牛客[NOIP2016]蚯蚓

题目链接：[NOIP2016]蚯蚓 (nowcoder.com)

目录

题目主要思路即注意操作：

1.如何快速找到目前队列中最长的那一根蚯蚓

2.如何对蚯蚓进行加长度的功能

题目主要思路即注意操作：

思路：

一道队列的题

该题对于我们主要的问题是如何

1.如何快速找到目前队列中最长的那一根蚯蚓

我们可以通过题目发现

对于每一次剪切后的蚯蚓

如果将剪切后长度为 px 和 x-px 的蚯蚓

用队列q1 和 q2 分别push的话

会发现两个队列都是从大到小排列

故每次我们只需要每次比较

剩余未被剪的蚯蚓 和 q1队首 和 q2队首

中的最大元素即可

2.如何对蚯蚓进行加长度的功能

因为每秒蚯蚓都会加长

我们可以加到某个状态的加了多少次

把它记录下来

并且记住每次取最长的蚯蚓的时候

需要把它的长度 加上 蚯蚓生长的长度

每次把被剪的两只蚯蚓放入队列的时候

需要把它的长度 减去 蚯蚓生长的长度

代码详解：

#include<iostream>
using namespace std;
#include<queue>
#include<algorithm>
queue<int> q1,q2;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int a[(int)1e5+6];
int n, m, q, u, v, t, tmb,ti;
int maxx(void)//找最大操作
{
    int ans=-1e9;
    if(ti<=n) ans=a[ti];
    if(!q1.empty()) ans=max(ans,q1.front());
    if(!q2.empty()) ans=max(ans,q2.front());
    if(ti<=n&&ans==a[ti]) ti++;
    else if(!q1.empty()&&ans==q1.front()) q1.pop();
    else q2.pop();
    return ans;
}
int main() {
    IOS;
    cin >> n >> m >> q >> u >> v >> t;
    double p = (u * 1.0) / (v * 1.0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a+1,a+1+n,greater<int>());//对原序列进行排序
    ti=1;
    int AddLen = 0;//记录蚯蚓生长的长度
    for (int i = 1; i <= m; i++) {
        int x = maxx()+AddLen;
        if(i%t==0) cout<<x<<" ";
        int len = p * x;
        AddLen += q;
        q1.push(len-AddLen);
        q2.push(x - len-AddLen);
    }

    cout << endl;
    for (int i = 1; i <= (n + m); i++) {
        int x=maxx() + AddLen ;
        if (i % t == 0) {
            cout << x<< " ";
        }
    }
    return 0;
}

PS:题目还是有点搞心态的，细节太多了，模拟起来倒是有点麻烦，so，加油