P2827 蚯蚓

Sym_Je · 2018-09-22 21:04:46 · 题解

             P2827 蚯蚓        

P2827 蚯蚓
首先这道题我们第一眼就可以发现，这个题似乎可以用堆，每次找到最大的，拆开扔进去，就?咯，他说其他的会加p，直接把拆开的每个减p，最后输出时加上已经经过的次数×p,就?咯。
但只有八十分。。。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;

int n,m,q,u,v,t;

double p;

priority_queue<int,vector<int>,less<int> > Q;

int main()
{
    freopen("a.in","r",stdin);
    freopen("a.ans","w",stdout);
    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
    double p=1.0*u/v;
    for(int i=1;i<=n;i++) 
    {
        int x;
        scanf("%d",&x);
        Q.push(x);
    }
    //cout<<p<<endl;
    for(int i=1;i<=m;i++)
    {
        if(i%t==0)
        {
            printf("%d ",Q.top()+(i-1)*q); 
        }
        int f=Q.top()+(i-1)*q;
        int x1=f*p;
    //  cout<<f<<"*"<<endl;
    //  cout<<x1<<endl;
        int x2=f-x1;
        x1-=i*q;
        x2-=i*q;
        Q.pop();
        Q.push(x1);
        Q.push(x2);
    }
    printf("\n");
    int i=1;
    while(!Q.empty())
    {
        if(i%t==0)
        {
            printf("%d ",Q.top()+m*q);
        }
        i++;
        Q.pop();
    }
    return 0;
}

这个题我们发现用了堆，复杂度还是过不去，常数有点大，所以我们在考虑一下，如果我们把最大按比例拆开后每个-p，之后，第二大的也是拆开再减，我们就可以发现，每次拆开的对应起来，永远是越大的拆开越大，符合单调性，因此维护三个数组就?咯。
a[]原先数组，从大到小。
b[] a[i]×p
c[] a[i]-b[i]
都具有单调性
每次比较每个数组里最大的，然后在拆开分放入b[],c[]中就?咯。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;

int n,m,q,u,v,t;


int a[11150001],b[11150001],c[11150001];

int ta,tb,tc;
int wa,wb,wc;

int num=0;

bool cmp(int a,int b)
{
    return a>b;
}

int main()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    tb=ta=tc=1;

    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1,cmp);
    wa=n;
    for(int i=1;i<=m;i++)
    {
        int maxx=-2147483626;
        int cc=0;
        if(maxx<a[ta]&&ta<=wa)
        {
            cc=1;
            maxx=a[ta];
        }
        if(maxx<b[tb]&&tb<=wb&&tb)
        {
            cc=2;
            maxx=b[tb];
        }
        if(maxx<c[tc]&&tc<=wc&&tc)
        {
            cc=3;
            maxx=c[tc];
        }
        //cout<<maxx<<"*"<<endl;
        //return 0; 
        if(i%t==0)
        {
            printf("%d ",maxx+(i-1)*q);
        }
        //cout<<cc<<endl;
        if(cc==1)
        {
    //      cout<<"2333";
            ta++;
            maxx+=(i-1)*q;
            int x1=maxx*1.0*u/v;
            int x2=maxx-x1;
            //cout<<x2<<endl;
            //return 0;
            b[++wb]=x1-q*i;
            c[++wc]=x2-q*i;
        }
        else if(cc==2)
        {
            tb++;
            maxx+=(i-1)*q;
            int x1=maxx*1.0*u/v;
            int x2=maxx-x1;
            b[++wb]=x1-q*i;
            c[++wc]=x2-q*i;
        }
        else if(cc==3)
        {
            tc++;
            maxx+=(i-1)*q;
            int x1=maxx*1.0*u/v;
            int x2=maxx-x1;
            b[++wb]=x1-i*q;
            c[++wc]=x2-i*q;
        }
    /*  cout<<"******************"<<endl;
        for(int i=1;i<=ta;i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<endl;
        for(int i=1;i<=tb;i++)
        {
            cout<<b[i]<<" ";
        }cout<<endl;
        for(int i=1;i<=tc;i++)
        {
            cout<<c[i]<<" ";
        }cout<<endl ;*/
    //  cout<<maxx<<"*"<<endl;
    }
    printf("\n");
    for(int i=1;i<=n+m;i++)
    {
        int maxx=-2147483476;
        int cc=0;
        if(maxx<a[ta]&&ta<=wa)
        {
            cc=1;
            maxx=a[ta];
        }
        if(maxx<b[tb]&&tb<=wb)
        {
            cc=2;
            maxx=b[tb];
        }
        if(maxx<c[tc]&&tc<=wc)
        {
            cc=3;
            maxx=c[tc];
        }
        if(i%t==0)
        {
        //  cout<<"2333";
    //      cout<<maxx<<endl;
            printf("%d ",maxx+m*q);
        }
        if(cc==1)
        {
            ta++;
        }
        if(cc==2)
        {
            tb++;
        }
        if(cc==3)
        {
            tc++;
        }
    }
    return 0;
}

附赠对拍器

gen

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<cstdlib>

using namespace std;

int main()
{
    freopen("a.in","w",stdout);
    srand(time(0)+2004); 
    int n,m,q,u,v,t;
    n=rand()%2004030+1,m=rand()%2200030,q=rand()%2222220,u=rand()%22222220,v=rand()%2222220,t=rand()%222222222; 
    printf("%d %d %d %d %d %d\n",n,m,q,u%v,v,t);
    for(int i=1;i<=n;i++)
    {
        if(i%10==0)
        cout<<endl;
        int x=rand()%22222220;
        printf("%d ",x);
    } 
    printf("%d\n");
    return 0;
}

pai

@echo off
:loop
gen.exe
bao.exe
zheng.exe
fc a.ans a.out 
if not errorlevel 1 goto loop
pause 
goto loop