补提交
Description
TOM给自己定了一个宏伟的目标：连续100天每天坚持在zcmu上提交一个程序。100天过去了，tom查看自己的提交记录发现有N天因为贪玩忘记提交了。于是TOM要来M张"补提交卡"。每张"补提交卡"都可以补回一天的提交，将原本没有提交程序的一天变成有提交程序的一天。tom想知道通过利用这M张补提交卡，可以使自己的"最长连续提交天数"最多变成多少天。
第一行是一个整数T(1 <= T <= 10)，代表测试数据的组数。
每个测试数据第一行是2个整数N和M(0 <= N, M <= 100)。第二行包含N个整数，表示第a1, a2, ... aN天TOM没有提交程序。ai<=100
Output
对于每组数据，输出通过使用补提交卡TOM的最长连续提交天数最多变成多少。
Sample Input
3
5 1
34 77 82 83 84
5
2
10
30 55 56 90
5
10
10 30 55 56 90
Sample Output
76
59
100
解题思路：100天的时间可以理解成一根数轴，那么出现的那几天没有提交的天数，就是数轴上的断点，现在我们得到的补签卡，就可以把数轴上的断点给补上，那么要如何选择要补上的断点呢？
以样例一分析：
断点： 34 77 82 83 84
1———‘——————’————‘ ’ ‘———100
中间值： 33 42 4 0 0 15 （中间值也就是TOM提交过的那些天数）
在这个示意图上可以很清晰的看到，我们的1张补签卡就是就是选择一个断点补上，将两段合为一段，然后期望这一段是最长的线段，那么有哪些结果呢？ 由上图可以看出 33+42 ， 42+4， 4+0， 0+0，0+15是所有连续两段的和。
明显，我们会选择34，因为33+42的和是最大的。
由此可以推得，如果是两张补签卡，那么我们就要补两个断点，自然，填补的这两个点肯定是要连续的才能得到最长的线段，那么我们也就是得到了连续三段线段和的最大值，这也就是我们求的答案了。继续推，如果是M（M<N)
张 补签卡，我们就需要 填补 M个 断点 ，求得连续M+1段线段和的最大值。
若M>=N,所有断点都能补上，答案肯定就是100了。
中间值的计算应该很容易做到，详见代码了。
这个方法可能不是最优的，但是应给比较容易理解，希望你看完之后能AC这道题。
</pre><pre name="code" class="cpp"><pre name="code" class="cpp">#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int repeat;
cin>>repeat;
while(repeat--)
{
int sub[105],day[105];
int i,k,n,m,b;
cin>>n>>m;
for(i=0;i<n;i++)
{
cin>>day[i];//断点
}
if(m>=n)
{
cout<<"100"<<endl;
continue;
}
sort(day,day+n);
for(i=0;i<n;i++)
{
if(i==0)
sub[i]=day[i]-1;
else
sub[i]=day[i]-day[i-1]-1;
}
sub[i]=100-day[i-1];//计算中间值
// for(i=0;i<=n;i++)
// cout<<sub[i]<<' ';
// cout<<endl;
int ans=0,sum=0;
for(i=0;i<=n-m;i++)
{
sum=0;
for(k=i;k<=i+m;k++)//求M+1段线段的和
{
sum+=sub[k];
}
if(ans<sum)
ans=sum;
}
cout<<ans+m<<endl;
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-1295394.html
