首页 > 代码库 > [7.8]烤鱼
[7.8]烤鱼
小x掉到了一个jzyz的窨井里，这口井很深，没有人能听到小x的呼救，悲催的小x必须要等D天后，学校确认他失踪才会大规模寻找他，而这难熬的D天将是小x这一生最难过的D天。
不过幸运的是小x在井里得到了N (1 <= N <= 50,000) 条鱼,编号1..N.他计划在接下来的D (1 <= D <= 50,000)天按鱼的编号从小到大逐天吃，当然，小x可以一天连续吃多条鱼，也可以不吃。
为了不浪费，小x要求鱼必须吃完。。并且剩下的鱼必须在最后一天都吃掉。
对于第i条鱼，小x的能量值会增加Hi(1 <= Hi <= 1,000,000)。小x会在白天吃鱼，一旦吃饱，他就会一觉睡到第二天。第二天醒来，她的能量值会变成前一天的能量值的一半（向下取整），小x的能量值是可以累加的。
小x比较注意维护每天能量的平衡，要刻意避免能量的大起大落，于是现在小x想知道，如何安排吃鱼，才能保证能量值最小的那个晚上(假设是第X个晚上)，第X个晚上的能量值最大。
例如：有5条鱼，能量值分别是： (10, 40, 13, 22, 7).
小x按以下方式吃鱼，将会得到最优值:
第几天 醒来时能量值 吃的鱼的能量值 晚上睡觉能量值
1 0 10+40 50
2 25 --- 25
3 12 13 25
4 12 22 34
5 17 7 24
可以看出，第1天吃了鱼1、鱼2，第2天不吃鱼，第3天吃了鱼3，第4天吃了鱼4，第5天吃了鱼5。 那么在这5个晚上，能量值最低的是第5个晚上，能量值是24，所以输出24。然后你还要输出第I (1<=i<=N)条鱼是小x第几天吃掉的.
题解：二分答案；
#include<iostream>#include<cstring>#include<cstdio>#include<cstdlib>#include<algorithm>#include<iomanip>#include<map>#include<set>#include<vector>#include<ctime>#include<cmath>#define LL long long using namespace std;#define LL long long #define up(i,j,n) for(int i=(j);(i)<=(n);(i)++)#define max(x,y) ((x)<(y)?(y):(x))#define min(x,y) ((x)<(y)?(x):(y))#define FILE "1"namespace OI{ const int maxn=51000; const LL inf=1000000000000LL; LL a[maxn],v[maxn],c[maxn],n,m; void init(){ freopen("1.in","r",stdin); freopen("1.out","w",stdout); scanf("%d%d",&m,&n); up(i,1,m)scanf("%I64d",&v[i]); } bool check(LL mid){ int now=1; up(i,1,n){ a[i]=a[i-1]/2; while(a[i]<mid&&now<=m)a[i]+=v[now++],c[now-1]=i; if(a[i]>=mid)continue; if(now>m)return 0; } up(i,now,m)c[i]=n; return 1; } void work(){ LL left=0,right=inf,mid,ans; while(left<=right){ mid=(left+right)>>1; if(check(mid))ans=mid,left=mid+1; else right=mid-1; } check(ans);ans=inf; up(i,1,n)ans=min(ans,a[i]); printf("%I64d\n",ans); up(i,1,m)printf("%d\n",c[i]); } void slove(){ init(); work(); }}int main(){ using namespace OI; slove();}
[7.8]烤鱼