AcWing 133/洛谷2827 蚯蚓

首先考虑根据题意模拟

#include<bits/stdc++.h>
#define int long long//懒死谁了
using namespace std;
typedef long long ll
inline void rd(int &x) {
    x=0;
    bool w=0;
    char ch1;
    ch1=getchar();
    while(!isdigit(ch1)) {
      ch1=='-'&&(w=1);
      ch1=getchar(); 
    }
    while(isdigit(ch1)) { 
      x=(x<<1)+(x<<3)+(ch1&15);
      ch1=getchar();
    }
    w&&(x=(~x)+1);
}
priority_queue<int>q;//只用一个优先队列维护所有蚯蚓长度
signed main()
{
//    freopen("test.in","r",stdin);
//    freopen("test.out","w",stdout);
    int n,m,qq,u,v,t,a;
    //n蚯蚓数 m剩余时间 q增加的长度  p=u/v  t每t次输出一次
//    scanf("%d%d%d%d%d%d",&n,&m,&qq,&u,&v,&t);
    rd(n);rd(m);rd(qq);rd(u);rd(v);rd(t);
    for(int i=1;i<=n;i++)
    {
//        scanf("%d",&a);//蚯蚓初始长度
        rd(a);
        q.push(a);//扔进去！
    }
    int delta=0;//维护一个delta 队列中的蚯蚓长度+delta为真实长度
    for(int i=1;i<=m;i++)
    {
        int s=q.top()+delta;//最长的蚯蚓长度
        q.pop();//别忘了qwq
        int ss=s*u/v;//被切断后的长度
        q.push(ss-delta-qq);
        q.push(s-ss-delta-qq);
        delta+=qq;
        if(i%t==0) 
        printf("%lld ",s);//t次了就输出
    }
    printf("\n");
    for(int i=1;q.size();i++)
    {
        int tt=q.top()+delta;
        q.pop();
        if(i%t==0)
        printf("%lld ",tt);
        //刚开始变量名重了.....
    }
    return 0;
}

预计得分80  实际得分85

似乎正解但是被AcWing卡了：

用三个队列维护  最后全部push进优先队列里

洛谷100 AcWing差一个点

//和正解很像 正解写了详细注释 这个就不写了
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int maxn=7e7+9;
int a[maxn],b[maxn],c[maxn];
priority_queue<int>q;
bool comp(int a,int b)
{
    return a>b;
}
int t0,t1,t2,h=1,h1=1,h2=1,cnt,delta;
signed main()
{
    int n,m,qq,u,v,t;
    scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&qq,&u,&v,&t);
    for(t0=1;t0<=n;t0++)
    {
        scanf("%lld",&a[t0]);
    }
    sort(a+1,a+n+1,comp);
    t0--;
    for(int i=1;i<=m;i++)
    {
        if(h>t0) {
            if(b[h1]>c[h2]) {
                cnt=b[h1++];
            }
            else {
                cnt=c[h2++];
            }
        }
        else if(a[h]>=b[h1]&&a[h]>=c[h2]) {
            cnt=a[h++];
        }
        else if(b[h1]>=c[h2]&&a[h]<=b[h1]) {
            cnt=b[h1++];
        }
        else {
            cnt=c[h2++];
        }
        cnt+=delta;
        int a1=u*cnt/v;
        int a2=cnt-a1;
        delta+=qq;
        a1-=delta;
        a2-=delta;
        b[++t1]=a1;
        c[++t2]=a2;
        if(i%t==0) {
            printf("%lld ",cnt);
        }
    }
    printf("\n");
    //全部push进堆里
    for(int i=h;i<=t0;i++)
    {
        q.push(a[i]);
    }
    for(int i=h1;i<=t1;i++)
    {
        q.push(b[i]);
    }
    for(int i=h2;i<=t2;i++)
    {
        q.push(c[i]);
    }
    for(int i=1;q.size();i++)
    {
        if(i%t==0) {
            printf("%lld ",q.top()+delta);
        }
        q.pop();
    }
    return 0;
}

正解：

用一次排序保证单调 用三个队列维护长度

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e7+10;
queue<ll>p1,p2,p3;
//q1原蚯蚓队列  q2切断后的左半段蚯蚓队列   q3右半段
int n,m,q,t;
ll a[maxn],u,v;
bool comp(ll a,ll b)
{
    return a > b;
    //将最长的放在队首
}
int find(int t)
//在三个队列里查找最长的蚯蚓长度
//t是已经经过了t秒
{
    int x=-1,a=-1,b=-1,c=-1;
    //全部赋初值防止有队列已空出错
    //可能存在长度为0的蚯蚓 所以初值是-1
    if(!p1.empty()) {
        a=p1.front()+t*q;
    }
    if(!p2.empty()) {
        b=p2.front()+t*q;
    }
    if(!p3.empty()) {
        c=p3.front()+t*q;
    }
    //取出每个队首
    x=max(a,max(b,c));//比较
    if(x==a) {
        p1.pop();
    }
    else if(x==b) {
        p2.pop();
    }
    else if(x==c) {
        p3.pop();
    }
    //找出属于哪个队列并弹出队列
    return x;
}
signed main()
{
    scanf("%d%d%d%lld%lld%d",&n,&m,&q,&u,&v,&t);
    //n为初始蚯蚓个数 m为一共切几次蚯蚓  q为每次增加的长度  
    //切成多少u/v和1-u/v两段  t是每几次输出一次
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        //输入初始蚯蚓长度
    }
    sort(a+1,a+1+n,comp);
    //排序 找最长的蚯蚓
    for(int i=1;i<=n;i++)
    {
        p1.push(a[i]);
        //将初始蚯蚓长度存进队列
    }
    for(int i=1;i<=m;i++)//每秒战况
    {
        ll x=find(i-1);
        if (!(i%t)) {
            printf("%lld ",x);
        }
        ll s1=x*u/v;
        ll s2=x-s1;
        //被切断后的两段蚯蚓长度 
        p2.push(s1-i*q);
        p3.push(s2-i*q);
        //由于q1内的蚯蚓长度是单调的 并且u/v的值没变  
        //所以切断后的蚯蚓长度也是单调的 用队列维护就行
    }
    printf("\n");
    for(int i=1;i<=(n+m);i++)
    //初始n条 每秒增加一条 经过m秒 所以一共有n+m条蚯蚓
    {
        ll x=find(m);
        //按从长到短的顺序每t个输出一次
        if (!(i%t)) {
            printf("%lld ",x);
        }
    }
    return 0;
}