有(m)种糖，每天吃一个。给出(a_i)，设(f_i=frac{a_i}{sum a_i})。
吃(n)天时，记(s_i)为第(i)种糖吃的总次数。此时满足：(nf_i-1<s_i<nf_i+1)。
给出一开始(k)天吃了什么糖，问满足这个限制还能吃多少天，或者forever。
(m,sum a_ile 10^5)
为了方便记(S=sum a_i)。
显然可以想到贪心：求出每种糖最早的使其不合法的(n)，每次取出这个值最小的糖，于是当天吃这种糖。先假装是这样。这显然是最优的。
另外说明一下可行性：可能取出这种糖，吃了之后会越过上界；但是这没有影响，如果吃了这颗糖会越过上界，那么暂时不吃这颗糖也不会越过下界，此时可以吃随便哪一种，然而这颗糖迟早是要吃的，先假装是“暂时”吃了它。实际上此时必然存在一种糖，吃了它之后一定不会越过上界（证明考虑由(sumfrac{s_i}{n}=sum frac{a_i}{S}=1)，得出(exist s_ileq frac{na_i}{S})，这个一定合法）。感受一下它是对的。
由于在(S|n)时每个(s_i)的取值是固定的，这就相当于是个循环节，后面的都模仿前面的操作即可。于是只需要做至多(S)次，即可判断是否forever。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#define N 100005
#define ll long long
int n,k;
int a[N],S;
int c[N];
int h[N],nh;
bool cmph(int x,int y){
return (ll)(c[x]+1)*S*a[y]>(ll)(c[y]+1)*S*a[x];
};
int main(){
// freopen("in.txt","r",stdin);
scanf("%d%d",&n,&k);
for (int i=1;i<=n;++i)
scanf("%d",&a[i]),S+=a[i];
for (int i=1,x;i<=k;++i)
scanf("%d",&x),c[x]++;
for (int i=1;i<=n;++i)
h[nh++]=i;
make_heap(h,h+nh,cmph);
int k_=k;
while (k%S){
int x=h[0];
pop_heap(h,h+nh--,cmph);
k++,c[x]++;
h[nh++]=x;
push_heap(h,h+nh,cmph);
if ((ll)k*a[h[0]]>=(ll)(c[h[0]]+1)*S/* || (ll)k*a[x]<=(ll)(c[x]-1)*S*/){
printf("%d
",k-1-k_);
return 0;
}
}
printf("forever
");
return 0;
}