题解 P2827 【蚯蚓】

方程_ · 2019-09-21 21:50:48 · 题解

因为每次操作后都要为其它数+=q

做个等价变换即可，让当前数-=q

回头再把该加的加上

85分

优先队列维护 原理很简单，每次取出最长的，切开，放进去

代码：

//头文件略
using namespace std;
void read(int &x);
const int MAXN=(int)1e5+5;
const int MAXM=(int)7e6+5;
int n,m,u,v,q,t;
double p;
int ans1[MAXM];
priority_queue<int> pq;
int main() {
    cin>>n>>m>>q>>u>>v>>t;
    p=(double)u/v;
    for(int i=1,x; i<=n; ++i) {
        read(x);
        pq.push(x);
    }
    int delta=0;
    for(int i=1; i<=m; ++i) {
        int x=pq.top();
        pq.pop();
        x+=delta;
        ans1[i]=x;
        int px=p*x;
        pq.push(px-delta-q);
        pq.push(x-px-delta-q);
        delta+=q;
    }
    for(int i=t; i<=m; i+=t)
        cout<<ans1[i]<<" ";
    cout<<endl;
    int count=1;
    while(!pq.empty()) {
        if(count%t==0)
            cout<<pq.top()+delta<<" ";
        pq.pop();
        count++;
    }
    return 0;
}
void read(int &x) {
    x=0;
    int f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=x*10+ch-'0';
        ch=getchar();
    }
    x*=f;
}

100分

实际上这道题有个隐含的单调性,即一个长的切成两半后，这两半

分别比后来切的短蚯蚓的两半长.用一个队列为原始数据，另开两

个队列分别保存两半

设x>=y,0<p<1其中的不等式为[px]+q=[px+q]>=[py+pq]=[p(y+q)]

另一半也是显然的,可以设p2=1-p,证明方法同上，当然也可以：

x-y>=p(x-y) => x-px>=y-py>=y-p(y+q) 进一步有

x-[px]+q=[x-px]+q>=[y-p(y+q)]+q=y+q-[p(y+q)]

代码：

#include <略>
using namespace std;
void read(int &x);
const int MAXN=(int)1e5+5;
const int MAXM=(int)7e6+5;
int n,m,u,v,q,t;
double p;
int ans1[MAXM],a[MAXN];
queue<int> q1,q2,q3;
inline int GetMax();
int main() {
    cin>>n>>m>>q>>u>>v>>t;
    p=(double)u/v;
    for(int i=1; i<=n; ++i)
        read(a[i]);
    sort(a+1,a+n+1,greater<int>());
    for(int i=1; i<=n; ++i)
        q1.push(a[i]);
    int delta=0;
    for(int i=1; i<=m; ++i) {
        int x=GetMax();
        x+=delta;
        ans1[i]=x;
        int px=p*x;
        q2.push(px-delta-q);
        q3.push(x-px-delta-q);
        delta+=q;
    }
    for(int i=t; i<=m; i+=t)
        cout<<ans1[i]<<" ";
    cout<<endl;
    int count=1;
    while(!q1.empty()||!q2.empty()||!q3.empty()) {
        int x=GetMax();
        if(count%t==0)
            cout<<x+delta<<" ";
        count++;
    }
    return 0;
}
inline int GetMax() {
    int x1=INT_MIN,x2=INT_MIN,x3=INT_MIN;
    if(!q1.empty())
        x1=q1.front();
    if(!q2.empty())
        x2=q2.front();
    if(!q3.empty())
        x3=q3.front();
    if(x1>=x2&&x1>=x3) {
        q1.pop();
        return x1;
    } else if(x2>=x3) {
        q2.pop();
        return x2;
    } else {
        q3.pop();
        return x3;
    }
}
void read(int &x) {
    x=0;
    int f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=x*10+ch-'0';
        ch=getchar();
    }
    x*=f;
}