首页 › 题库 › C/C++编程考级 › C/C++编程三级 › 简答题
简答题 偏难
#7376

苹果消消乐 有100个苹果和香蕉排成一条直线,其中有N个香蕉,你可以使用至多M次魔法道具将香蕉变成苹果,最后“最长的连续苹果数量”即为你本次苹果消消乐的得分,给…

苹果消消乐

有100个苹果和香蕉排成一条直线,其中有N个香蕉,你可以使用至多M次魔法道具将香蕉变成苹果,最后“最长的连续苹果数量”即为你本次苹果消消乐的得分,给定苹果和香蕉的排列,求你能获得的最大得分。

时间限制:1000

内存限制:65536

输入

第一行是一个整数T(1 <= T <= 10),代表测试数据的组数。 每个测试数据第一行是2个整数N和M(0 <= N, M <= 100)。第二行包含N个整数a1, a2, ... aN(1 <= a1 < a2 < ... < aN <= 100),表示第a1, a2, ... aN个位置上摆放的是香蕉。

输出

对于每组数据,输出通过使用魔法道具后你能获得的最大得分。

样例输入

3
5 1
34 77 82 83 84
5 2
10 30 55 56 90
5 10
10 30 55 56 90

样例输出

76
59
100

提示

这是个枚举题

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//解法1 #include&lt;bits/stdc++.h&gt; using namespace std; //计算最大长度 void fun(int n,int m,int a[]){  int ma=0;  if(m&gt;=n)ma=100;//如果道具次数大于香蕉的个数,能把香蕉全变成苹果,不用算,直接得100   else {   int s;   for(int i=m+1;i&lt;=n+1;i++){//3 2 10 50 90    s=a[i]-1-a[i-m-1];    if(s&gt;ma)ma=s;   }  }  cout&lt;&lt;ma&lt;&lt;endl;  }  int main(){  int t,n,m,i,j;//n个香蕉,m个道具,t组数据  cin&gt;&gt;t;  for(i=1;i&lt;=t;i++){   cin&gt;&gt;n&gt;&gt;m;   int a[102]={0};   for(j=1;j&lt;=n;j++)cin&gt;&gt;a[j];//香蕉的位置   a[0]=0;//在最前面和最后面添加一个香蕉   a[n+1]=101;   fun(n,m,a);  }  return 0; }</pre><p><br/></p><pre class="brush:cpp;toolbar:false">//解法2  模拟+尺取 #include &lt;iostream&gt; #include &lt;cstring&gt; using namespace std; int a[102]; int main(){ int t,n,m,maxn; cin&gt;&gt;t; while(t--){ memset(a,0,sizeof(a)); maxn=0; cin&gt;&gt;n&gt;&gt;m; if(m&gt;=n) {cout&lt;&lt;100&lt;&lt;endl;continue;} for(int i=1;i&lt;=n;i++) cin&gt;&gt;a[i]; a[n+1]=101; for(int i=1;i+m-1&lt;=n;i++) maxn=max(maxn,a[i+m]-a[i-1]-1); cout&lt;&lt;maxn&lt;&lt;endl; } return 0; }</pre>
这道题暂未补解析。