简答题 偏难
#7130

苹果消消乐 有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">#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><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>
这道题暂未补解析。