链接: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; }
|
近期评论