大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。
题目描写叙述开头一大堆屁话,我还细致看了半天。。事实上就最后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;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/118673.html原文链接:https://javaforall.cn