洛谷 P2827蚯蚓 队列优化

题目：https://www.luogu.org/problem/show?pid=2827

简单讲一下

就是有一群数
每次找到最大的一个按一定比例切成两段
还要模拟，并且按一个规则输出一些东西

怎么办呢

使用队列优化
读入，从大到小排好序塞进一个队列
每次切开的分到另外两个队列里
三个队列都是单调递减的
（手动比划一下就知道了其实是博主懒得证明）
所以每次拿三个队头比较
挑一个最大的正常切就行了

代码片

#include<cstdio>
#include<algorithm>
#define maxn 8000000
int que[4][maxn], h[4], t[4];
int n, m, q, u, v, ti, sum, i, j, time;
inline bool cmp(int x, int y) {
    return x > y;
}
inline void read(int& x) {
    char ch;
    for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar());
    for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = x*10 + ch-'0';
}
int main() {
    read(n); read(m); read(q); read(u); read(v); read(ti);
    for(i = 1; i <= n; i++) read(que[1][i]);
    std::sort(que[1]+1, que[1]+n+1, cmp);
    h[1] = h[2] = h[3] = 1;
    t[1] = n; t[2] = t[3] = 0;
    for(i = 1; i <= m; i++) {
        int mi = -1, mx = 0x80000000, x1, x2;
        for(j = 1; j <= 3; j++) if(h[j] <= t[j] && que[j][h[j]] > mx) mi = j, mx = que[j][h[j]];
        h[mi]++; mx += sum; sum += q;
        x1 = (int)((long long)mx*u/v); x2 = mx - x1; x1 -= sum; x2 -= sum; 
        que[2][++t[2]] = x1; que[3][++t[3]] = x2;
        if(++time == ti) printf("%d ", mx), time = 0;
    } putchar('\n');
    for(i = 1, time = 0; i <= m+n; i++) {
        int mi = -1, mx = 0x80000000, x1, x2;
        for(j = 1; j <= 3; j++) if(h[j] <= t[j] && que[j][h[j]] > mx) mi = j, mx = que[j][h[j]];
        h[mi]++;
        if(++time == ti) printf("%d ", mx+sum), time = 0;
    } putchar('\n');
}

另外

这道题为了卡时间可以说是不择手段的
懒得卡常数的可以用氧气（O2）优化
虽然可能会气死Pascal党
或者搞一下读入，搞一下取模，调一下赋值……

附上O2优化过的代码一份

#pragma GCC optimize("O2")
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 8000000;
const int INF = 2147483647;
int que[4][maxn], h[4], t[4];
int n, m, q, u, v, ti, sum;

int main() {
    scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &ti);
    for(int i = 1; i <= n; i++) scanf("%d", &que[1][i]);
    sort(que[1]+1, que[1]+n+1, greater<int>());
    h[1] = h[2] = h[3] = 1;
    t[1] = n; t[2] = t[3] = 0;
    for(int i = 1; i <= m; i++) {
        int mi = -1, mx = -INF, x1, x2;
        for(int j = 1; j <= 3; j++) if(h[j] <= t[j] && que[j][h[j]] > mx) mi = j, mx = que[j][h[j]];
        h[mi]++; mx += sum; sum += q;
        x1 = (int)((long long)mx*u/v); x2 = mx - x1; x1 -= sum; x2 -= sum; 
        que[2][++t[2]] = x1; que[3][++t[3]] = x2;
        if(i % ti == 0) printf("%d ", mx);
    } printf("\n");
    for(int i = 1; i <= m+n; i++) {
        int mi = -1, mx = -INF, x1, x2;
        for(int j = 1; j <= 3; j++) if(h[j] <= t[j] && que[j][h[j]] > mx) mi = j, mx = que[j][h[j]];
        h[mi]++;
        if(i % ti == 0) printf("%d ", mx+sum);
    } printf("\n");
    return 0;
}