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