2016

链接:https://codeforces.com/gym/101242/attachments
思路:把式子转一下,改成整数形式,然后维护一下还剩多少天可以不吃糖,优先取一个最近的出来就行了,如果取出来已经比当前天数小了,就说明不可行了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

using namespace std;

typedef long long ll;
typedef pair<ll, int> pii;
priority_queue<pii, vector<pii>, greater<pii> > q;
const int maxn = 1e5 + 5;
ll a[maxn], b[maxn];

int n, k;
ll sum;

pii (int j, int i){
return pii(((b[i] + 1) * sum - (k + j) * a[i] + a[i] - 1) / a[i] + j, i);
}

int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
for(int i = 1; i <= k; i++){
int x;
cin >> x;
b[x]++;
}
for(int i = 1; i <= n; i++)q.emplace(cal(0, i));
for(int i = 1; i <= sum + 1; i++){
pii p = q.top();
q.pop();
b[p.second]++;
q.emplace(cal(i, p.second));
if(q.top().first <= i){
cout << i - 1 << 'n';
return 0;
}
}
cout << "forevern";
return 0;
}