<==制作不易,求个赞QwQ
算法1
考虑到后边要输出第几组,所以我们不能用while(t--)
,需要for(int k=1;k<=t;k++)
一个检查点是山峰,如果满足:
- 它不是第 1 个或第 N 个检查点。
- 它的高度严格大于紧接其之前的检查点和紧接其之后的检查点。
我们可以得出一下代码:
for(int i=2;i<=n-1;i++){
if(a[i-1]<a[i]&&a[i+1]<a[i])c++;
}
最后我们按格式输出c
即可,记得每一轮下来要清零
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
for(int k=1;k<=t;k++){
int n,a[101],c=0;
//memset(a,0x3f,sizeof(a));
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=2;i<=n-1;i++){
if(a[i-1]<a[i]&&a[i+1]<a[i])c++;
}
cout<<"Case #"<<k<<": "<<c<<'\n';
}
}
以下为恶搞版
算法二
用结构体记录当前项的前一项和后一项,排完序后判断即可【其实就是加了一大堆废话】
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,l,r;
}a[101];
bool cmp(node a,node b){
return a.x<b.x;
}
int main()
{
int t;
cin>>t;
for(int k=1;k<=t;k++){
int n,c=0;
memset(a,0x3f,sizeof(a));
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i].x;
for(int i=2;i<=n-1;i++)a[i].l=a[i-1].x,a[i].r=a[i+1].x;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
if(a[i].l<a[i].x&&a[i].r<a[i].x)c++;
}
cout<<"Case #"<<k<<": "<<c<<'\n';
}
}
算法三
不用数组欸
我们先输入两个数,相当于前一项和当前项
由于我们已经输入两个数,所以for循环一直到n-2
我们输入的c
相当于后一项
每次输入完,我们按题目判断一下,然后替换即可
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
for(int k=1;k<=t;k++){
int n,a,b,c,ans=0;
cin>>n;
cin>>a>>b;
for(int i=1;i<=n-2;i++){
cin>>c;
if(a<b&&c<b)ans++;
a=b,b=c;//移动
}
cout<<"Case #"<<k<<": "<<ans<<'\n';
}
}
算法四
看到head
、top
、tail
你想到了什么?
好吧,这啥也不是
我们只是把前一项,当前项,后一项拿东西代替了一下
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
for(int k=1;k<=t;k++){
int n,ans=0,a[101];
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int head=1,top=2,tail=3;
while(head!=n-1&&top!=n&&tail!=n+1){//废话ing
if(a[head]<a[top]&&a[tail]<a[top])ans++;
head++,top++,tail++;
}
cout<<"Case #"<<k<<": "<<ans<<'\n';
}
}
算法五
写了一推关于队列的废话。。。
我们把队列的**头指针置为1
,把尾指针置为3
我们把第一个 和 第n个检查点的值给踢出,然后判断一下输出即可
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int q[101],head,tail;
void init(){
memset(q,0x3f,sizeof(q));
}
void push(int x){
q[++tail]=x;
}
void pop(){
head++;
}
int find(int x){
for(int i=head;i<=tail;i++){
if(q[i]==x)return i;
}
return -1;
}
int size(){
return tail-head+1;
}
int query(){
return q[head];
}
int seek(int x){
return q[x];
}
int minn(){
int minn=0x3f3f3f3f;
for(int i=head;i<=tail;i++){
minn=min(minn,q[i]);
}
return minn;
}
int maxx(){
int maxx=-0x3f3f3f3f;
for(int i=head;i<=tail;i++){
maxx=max(maxx,q[i]);
}
return maxx;
}
int main()
{
int t;
int c=0;
cin>>t;
while(t--){
c++;
int n,ans=0,head=1,tail=3;
cin>>n;
init();
for(int i=1;i<=n;i++)cin>>q[i];
while(head<=tail&&head<=n&&size()!=0){//size()!=0代表队列没有全被删除
if(find(q[head])==1)push(q[head]);//踢出
if(find(q[tail])==n)push(q[tail]);//踢出
if(q[head-1]<q[head]&&q[head+1]<q[head]&&head!=1&&head!=n)ans++;
head++,tail++;
}
cout<<"Case #"<<c<<": "<<ans<<'\n';
}
}
算法六
前缀和写法
我们计算前缀,这里有点绕人,我们不妨做个实验:(用样例)
5
10 90 20 90 10
当我们i
到了2
,a[i]
的值是90
,我们怎么得出前一项呢?我们就需要把前缀相减
也就是s[i-1]-s[i-2]
,我们把i=2
带入,那么s[0]
为0
,s[1]
为10
,所以相减等于10
10
比90
小,满足要求,以此类推,皆可……
我们怎么考虑右侧呢?其实我们还是把前缀相减
也就是s[i+1]-s[i]
,按照上面的类推,就可以得出后一项的值啦
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
int c=0;
cin>>t;
while(t--){
c++;
int n,a[101],s[101],ans=0;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],s[i]=s[i-1]+a[i];
for(int i=2;i<=n-1;i++)
if(s[i-1]-s[i-2]<a[i]&&s[i+1]-s[i]<a[i])ans++;
cout<<"Case #"<<c<<": "<<ans<<'\n';
}
}
算法七
后缀和,其实就是把上面的代码给反过来即可
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
int c=0;
cin>>t;
while(t--){
c++;
int n,a[101],s[101],ans=0;
cin>>n;
for(int i=n;i>=1;i--)cin>>a[i],s[i]=s[i+1]+a[i];
for(int i=n-1;i>=2;i--)
if(s[i+1]-s[i+2]<a[i]&&s[i-1]-s[i]<a[i])ans++;
cout<<"Case #"<<c<<": "<<ans<<'\n';
}
}
解法好多呀QWQQ
hhh
www二分怎么做
好难写QwQ
不过你的恶搞版着实是good啊
hhh
我正在尝试用队列写hhh
while可以用是可以用的hh,不过要定义组别编号
addd
对Saber不太友好hhh
确实
改好啦