首页 > 代码库 > hihocoder-1051-补提交卡
hihocoder-1051-补提交卡
小Ho给自己定了一个宏伟的目标：连续100天每天坚持在hihoCoder上提交一个程序。100天过去了，小Ho查看自己的提交记录发现有N天因为贪玩忘记提交了。于是小Ho软磨硬泡、强忍着小Hi鄙视的眼神从小Hi那里要来M张"补提交卡"。每张"补提交卡"都可以补回一天的提交，将原本没有提交程序的一天变成有提交程序的一天。小Ho想知道通过利用这M张补提交卡，可以使自己的"最长连续提交天数"最多变成多少天。
(0 <= N, M <= 100)
分析：贪心
要想连续的天数，不提交卡肯定用在连续的空缺上，所以枚举从第一个空缺开始连续m，从二个空缺开始连续m......以此类推
对于每次枚举起点我的做法是：用得把数组的相应空缺位置b[i]置0，遍历数组b[]，计算最大的连续天数
但是这次的枚举修改的b[]，下次枚举要改回来，所以我直接利用函数的值传参特性，所以数组用的vector<int> b而不是用int b[]，因为数组传参相当于指针传参，修改是有效的
1 #include<iostream> 2 #include<cstring> 3 #include<vector> 4 #include<algorithm> 5 using namespace std; 6 7 int t,n,m; 8 int a[200]; 9 10 11 int func(vector<int> b,int i)12 {13 int ans=0;14 for(int j=0;j<m;j++){15 b[a[i+j]]=0;16 }17 int sum=0;18 for(int i=1;i<=100;i++){19 if(b[i]==0) sum++;20 else{21 ans=max(ans,sum);22 sum=0;23 }24 }25 return ans;26 }27 28 int main()29 {30 cin>>t;31 while(t--){32 cin>>n>>m;33 vector<int> b(200);34 for(int i=0;i<n;i++){35 cin>>a[i];36 b[a[i]]=1;37 }38 if(n<=m) cout<<100<<endl;39 else{40 sort(a,a+n);41 int ans=0;42 for(int i=0;i+m-1<n;i++){43 ans=max(ans,func(b,i));44 }45 cout<<ans<<endl;46 }47 }48 }
hihocoder-1051-补提交卡
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。