A: Balanced Diet
問題
Dannyはm種類の菓子を一つづつ食べる。今までの菓子iを食べた個数をs_iとする。
各菓子iの個数は割合f_iに近い値にしたい。
正確には、今まで食べたお菓子の総数をnとすると、任意のお菓子iは
を満たす必要がある。
すでに、k個のお菓子を食べており、それらは度のタイミングでも条件を満たしている。
今後、最適な順番で菓子を食べることで、最大でいくつのお菓子を食べることができるか求めよ。
無限に食べることができるならばそれを指摘せよ。
制約
m <= 10^5
k <= 10^5
f_iは整数の比で与えられ、f_i := a_i / (sum a_i)
1 <= a_i
sum a_i <= 10^5
入力のk個の菓子を順番に食べる場合、上の条件を満たしている。
解法
まず、無限に食べることができる場合とはどのような状態か。
n f_i が整数のとき、その間の s_i が取りうる値は n f_i 丁度である必要がある。
そして、n が sum a_i の倍数のとき、全ての i について、s_i は一通り。
以降、同じ順番で s_i を増やしていけば無限に食べることができる。
よって、n がsum a_i の倍数に成るまで一つづつ増やしていき、到達したら無限ということで打ち切ればよい。
食べるべき菓子の条件を出す。
- 右2項 s_i < n f_i + 1 より: nを増加していくとある時点で s_i + 1 < n' f_i + 1 になり、n' 以降でs_iを増やしても良い。
- 左2項 n f_i - 1 < s_i より: nを増加していくとある時点で n' f_i - 1 > s_i になり、n' の前にs_iを増やす必要がある。
上の条件より、食べてもいいお菓子の集合が得られ、下の条件よりなるべく早く食べたいお菓子が得られる。
これらを2つの優先度付きキューで貪欲に取り、食べてもいい菓子がない場合・食べていい時間を過ぎてしまった菓子が出た場合そこで終わり。
sum a_iの倍数に成るまで食べたら無限。
コード
#include<queue> #include<cstdio> #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cstring> using namespace std; typedef long long LL; typedef vector<int> VI; #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i) #define eprintf(s...) fprintf(stderr, s) template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; } template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; } int K, M; int A[100111]; LL a_sum; LL S[100111]; pair<int, int> f(int i) { LL l, h; if (M == 1) { l = K+1; h = K+1; } else { l = K + (S[i] * a_sum - (LL)K * A[i]) / A[i] + 1; h = K + (a_sum * (S[i] + 1) - (LL)K * A[i] - 1) / A[i] + 1; amax(l, (LL)K+1); } if (l > h) return make_pair(-1, -1); else return make_pair(l, h); } int main() { scanf("%d%d", &M, &K); REP (i, M) { scanf("%d", A+i); a_sum += A[i]; } REP (i, K) { int x; scanf("%d", &x); x--; S[x]++; } int ans = 0; priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Q, R; REP (i, M) { pair<int, int> p = f(i); if (p.first < 0) { goto END; } p.second = i; Q.push(p); } while (K % a_sum) { while (!Q.empty() && Q.top().first <= K + 1) { pair<int, int> p = Q.top(); Q.pop(); int i = p.second; p = f(i); p = make_pair(p.second, i); R.push(p); } if (R.empty() || R.top().first <= K) { ans--; goto END; } pair<int, int> p = R.top(); R.pop(); int i = p.second; S[i]++; K++; ans++; p = f(i); if (p.first < 0) { goto END; } p.second = i; Q.push(p); } puts("forever"); return 0; END:; printf("%d\n", ans); return 0; }