P6917 [ICPC2016 WF]Balanced Diet

P6917 [ICPC2016 WF]Balanced Diet

每天,Danny 都会从糖果店买一颗糖并吃掉它。糖果店中有 mm 种糖,编号为 1 dots m1…m 。

Danny 知道均衡饮食很重要,他正在尝试在购买糖果时有一个均衡的饮食。因此他给每种糖 ii 分配了一个目标分数 f_i (0 le f_i le 1, f_if
i

(0≤f
i

≤1,f
i

为一个实数 )), 。他希望他所吃的所有糖中,第 ii 种糖的数量占比大概为 f_if
i

准确的说, 令 s_ is
i

表示 Danny 已经吃掉的第 ii 种糖的数量, n = sum {i=1}^ m s in=∑
i=1
m

s
i

, 我们认为一种吃糖的方法是均衡的仅当对于所有的 ii,满足:

n f_ i - 1 < s_ i < n f_ i + 1
nf
i

−1<s
i

<nf
i

+1

Danny 已经购买并吃掉了一些糖,并且他保证每个前缀的饮食都是均衡的。他想知道在保证每个前缀均衡饮食的条件下,他最多还能吃多少颗糖。

给定目标分数 f_if
i

和他已经吃过的糖果序列,请你确定在保证每个前缀均衡饮食的条件下,Danny 最多还能购买并吃掉多少颗糖果。

Solution

满足下界贪心即可,即我们需要满足,n为天数

[frac{na_{i}}{sf}lt s_{i}+1 ]

求解的是天数,即

[nltfrac{(s_{i} +1)sf}{a_{i}} ]

注意 (n) 为整数,所以

[nltlfloor frac{(s_{i} +1)sf}{a_{i}} floor + 1 ]

写成代码就长这样,主要原因是上面声明的时候,数据类型是 (ll)不是(double)

LL s = ((S[i] + 1)*sf + F[i] - 1) / F[i];

减一是为了恰好不进位
也就是说,想要把 2.0 变成 2, 把 2.1 变成3


那就说个例子:比如我算出来是2.1天,目前时间是2天
如果不加一的话,2.1就变成2了,可实际上这一天我还不用吃,还是满足下界不等式的
加一变成3就没问题了

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
#define LL long long
#define REP(i, x, y) for(LL i = (x);i <= (y);i++)
using namespace std;
LL RD(){
    LL out = 0,flag = 1;char c = getchar();
    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
    return flag * out;
    }
const LL maxn = 100010;
LL m, k, tot;
LL a[maxn], b[maxn];
priority_queue<pair<LL, LL> >Q;
void init(){
	m = RD(), k = RD();
	REP(i, 1, m){
		a[i] = RD();
		tot += a[i];
		}
	REP(i, 1, k){
		LL temp = RD();
		b[temp]++;
		}
	REP(i, 1, m){
		LL temp = ((b[i] + 1) * tot + a[i] - 1) / a[i];
		Q.push(make_pair(-temp, i));
		}
	}
void work(){
	LL i = k + 1;
	for(i;i <= k + tot;i++){
		LL day = -Q.top().first, Index = Q.top().second;
		Q.pop();
		if(day < i){
			i = day - 1;//目前的day天是无法满足的
			break;
			}
		b[Index]++;//吃糖
		day = ((b[Index] + 1) * tot + a[Index] - 1) / a[Index];
		Q.push(make_pair(-day, Index));
		}
	if(i != k + tot + 1)cout<<i - k<<endl;
	else puts("forever");
	}
int main(){
	init();
	work();
	return 0;
	}
原文地址:https://www.cnblogs.com/Tony-Double-Sky/p/14409824.html