题意
初始时有$n$个蚯蚓，每个长度为$a[i]$
有$m$个时间，每个时间点找出长度最大的蚯蚓，把它切成两段，分别为$a[i] * p$和$a[i] - a[i] * p$，除这两段外其他的长度都加一个定值$q$。
每次询问被蚯蚓被切前的长度
Sol
用堆模拟可获得$50 - 85$不等的分数。
蚯蚓的长度有单调性。然后这题就做完了。。。
首先把$a[i]$排序
我们分别维护三个数组$a, b, c$，分别表示未被切的蚯蚓，被切成$p * a[i]$的蚯蚓和被切成$a[i] - p * a[i]$的蚯蚓
然后每次取出这三个里面最大的，切开之后再插回去就行了
大概口胡一下单调性的证明：
这题中最重要的两个条件是$a_i$有序以及$0 < p < 1$
首先$a_i$有单调性是显然的
考虑$b, c$中的元素一定是按照从小到大的顺序加入的，且不受全局标记的影响。
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> const int MAXN = 1e7 + 10, INF = 1e9 + 10; using namespace std; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M, All, T, u, v, a[MAXN], p; queue<int> q[3]; bool comp(const int &a, const int &b) { return a > b; } int main() { N = read(); M = read(); All = read(); u = read(); v = read(); T = read(); p = u / v; for(int i = 1; i <= N; i++) a[i] = read(); sort(a + 1, a + N + 1, comp); for(int i = 1; i <= N; i++) q[0].push(a[i]); int cur = 0; for(int i = 1; i <= M; i++) { //if(i == 5) {printf("%d ", q[2].front());} int val = -INF, mx = 0; for(int j = 0; j < 3; j++) if(!q[j].empty() && q[j].front() > val) mx = j, val = q[j].front(); int top = val; q[mx].pop(); if(!(i % T)) printf("%d ", val + cur); q[1].push(1ll * (top + cur) * u / v - cur - All); q[2].push((top + cur) - 1ll * (top + cur) * u / v - cur - All); cur += All; } puts(""); priority_queue<int> ans; for(int i = 1; i <= N + M; i++) { int val = -INF, mx =0 ; for(int j = 0; j < 3; j++) if(!q[j].empty() && q[j].front() > val) mx = j, val = q[j].front(); q[mx].pop(); if(!(i % T)) printf("%d ", val + cur); } return 0; }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
