大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。
题目描写叙述开头一大堆屁话,我还细致看了半天。。事实上就最后2句管用。意思就是给出n本书然后要分成k份,每份总页数的最大值要最小。问你分配方案,假设最小值同样情况下有多种分配方案,输出前面份数小的,就像字典序输出从小到大一样的意思。
这里用到贪心的方法,定义f(x)为真的条件是满足x为最大值使n本书分成k份,那么就是求x的最小值。怎样确定这个x就是用的二分法,x一定大于0小于全部值的合,不断的二分再推断是否成立,成立就取左半边,不成立说明太小了就取右半边,写的时候还是没有把二分法理解透彻,我还怕会丢失那个值还特意去保存,其实二分法最后结束得出来的x或y(二个数是相等的)就是每份的最大值。而怎样确定这个最大值是否成立就是用贪心的方法,尽量的往右边拓展直到大于最大值的前一个为止。假设份数还没分完就到最后一个了,那就肯定是成立的。反之,假设份数分完了还没到最后一个那就是不成立。
输出的时候还得注意,得从后往前,由于前面的份数得要小,就得从后往前贪心,还有当剩余的跟份数一样的时候就不能贪心了,就要每个都要分开了。这个就自己模拟数据看吧,加一减一的都得跟前面写的有关系。
还有两点要特别注意, 求和的时候会超int范围,由于一个最大可达1×10^8,而最多有500个,超过了4×10^9了。所以要用long long。另一点是输出的时候最后一个数字后面不能多打一个空格不然会报PE的。
AC代码:
#include<cstdio> #include<ctype.h> #include<algorithm> #include<iostream> #include<cstring> #include<vector> #include<stack> #include<cmath> #include<queue> #include<set> #include<ctime> using namespace std; #define NMAX 505 #define ll long long int a[NMAX]; int ans[NMAX]; int solve(ll Max,int n,int k) { int i=0,j=0,nct=0; ll sum=0; while(nct < k) { sum+=a[j]; if(sum > Max && i == j) return 0; if(sum > Max) { nct++; i = j; sum = 0; } else j++; if(j == n) return 1; } return 0; } void path(ll Max,int n,int k) { int nct = 0,i=n-1; ll sum=0; while(i>0) { sum+=a[i]; if(sum > Max) { sum = 0; ans[i] = 1; nct++; } else i--; if(i == k-nct-2) { for(int j = 0; j <= i; j++) ans[j] = 1; break; } } for(int i = 0; i < n; i++) { if(i == n-1) printf("%d",a[i]); else printf("%d ",a[i]); if(ans[i]) printf("/ "); } printf("\n"); } int main() { int i,n,k,m; scanf("%d",&n); while(n--) { memset(ans,0,sizeof(ans)); scanf("%d%d",&m,&k); ll sum = 0; for(i = 0; i < m; i++) { scanf("%d",&a[i]); sum += a[i]; } ll x=0,y=sum,z; while(x<y) { z = x+(y-x)/2; if(solve(z,m,k)) y = z; else x = z+1; } path(x,m,k); } return 0; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118673.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...