RQNOJ 658(观光公交)

几大注意点:

1.一次使用氦气加速器会把后面分成好几段。

2.我们仅维护end[i],wait[i]恒定,因此需提前让wait[i]=max(wait[i-1],wait[i]);

3.w[i]+w[i+1]+…+w[j],且w恒定,故可预处理sum[i](满足累加性)

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<functional>
#include<iostream>
#define MAXN 1000 +10
#define MAXM 10000 + 10
#define MAXK 100000 + 10
#define MAXD 100 + 10
#define MAXT 100000 + 10
using namespace std;
struct man
{
    int t,l,r;
}t[MAXM];
struct interval
{
    int l,r,w;
};

int n,m,k,ans,d[MAXN+1],wait[MAXN+1],w[MAXN+1],end[MAXN+1],sum[MAXN+1];
bool operator<(const interval a,const interval b)   //重载  operator < 的意思   为q做准备   
{

    return a.w<b.w;  
}

priority_queue<interval> q;   //priority_queue<Node, vector<Node>, greater<Node> >; 完整的不能用 

void push(int l,int r)
{
    bool flag=0;
    for (int i=l;i<r;i++) if (d[i]) {flag=1;break;}
    if (!flag) return;
    int tot=sum[r]-sum[l];
    if (!tot) return ;
    interval now;
    now.w=tot;
    now.l=l;
    now.r=r;
    q.push(now);    

//   cout <<"add "<< now.l << ' ' << now.r <<' '<< now.w << endl;
}

int main()
{
//  freopen("qc.in","r",stdin);
    memset(wait,0,sizeof(wait));
    memset(w,0,sizeof(w));

    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n-1;i++)
        scanf("%d",&d[i]);
    for (int i=1;i<=m;i++)
    {   
        scanf("%d%d%d",&t[i].t,&t[i].l,&t[i].r);
        wait[t[i].l]=max(wait[t[i].l],t[i].t);  
        w[t[i].r]++;
    }
    end[1]=0;
    for (int i=2;i<=n;i++)
       end[i]=max(end[i-1],wait[i-1])+d[i-1];
    ans=0;
    for (int i=1;i<=m;i++)
       ans+=end[t[i].r]-t[i].t;

    sum[1]=sum[0]=0;
    for (int i=2;i<=n;i++) {sum[i]=sum[i-1]+w[i]; wait[i]=max(wait[i-1],wait[i]);}

//  for (int i=0;i<=n;i++) cout<<end[i]<<' ';
//  cout<<endl;

    int tot=d[1],head=1;
    for (int i=2;i<=n;i++)
    {
        if (wait[i]>=end[i]) 
        {
            if (tot) push(head,i);
            tot=0;
            head=i;         
        }
        tot+=d[i];
        /*  
        tot+=w[i]*min(1,d[i]);
//      tot+=w[i];
        */      
    }

    if (tot) push(head,n);

//00    cout<<ans<<endl;
    //贪心
//  sort(t+1,t+m+1,cmp);

// 调试 
/*   while( !q.empty() ){
        cout << q.top().l << ' ' << q.top().r <<' '<< q.top().w << endl;
        q.pop();
    }
*/  
/*  
    for (int i=1;i<=n;i++) 
    {
        cout<<end[i]<<' ';      
    }
*/  
    while (k&&!q.empty()) 
    {
/*  cout<<"/////////"<<endl;  
    for (int i=1;i<=n;i++) 
    {
        cout<<end[i]<<' ';      
    }
    cout<<endl;
    for (int i=1;i<=n;i++) 
    {
        cout<<wait[i]<<' ';     
    }

    cout<<endl;
*/  
        interval now=q.top();
        q.pop();
        ans-=now.w;
        int i=now.l;
//000
//     cout << now.l << ' ' << now.r <<' '<< now.w << endl;
//      cout << ans << endl;
//000

        while (!d[i]) i++; 
        d[i]--;  
        int head=i,tot=0,i2=0;
        i++;
        while (i<=now.r/*&&wait[i]<end[i]*/) 
        {       
        //  tot+=w[i-1];
            end[i]--;   
            //000
//          for (int cse=1;cse<=n;cse++) cout<<end[cse]<<',';
//          cout<<endl;
            //-
//          cout<<i<<endl;
//          cout<<wait[i+1]<<' '<<end[i+1]<<endl;
            if (wait[i]==end[i]) 
                {push(head,i);head=i;}
            i++;
        }

        i--;
        if (head!=now.r) push(head,now.r);

/*
        if (i>now.r) {cout<<"smile"<<endl;
            cout<<'<'<<' '<<i<<' '<<wait[i]<<' '<<end[i]<<' '<<endl;}
*/
//      cout<<"i2:"<<i2<<endl;
/*      if (i2) i=i2; 
        i--;
        push(head,i);
        if (i<now.r)
        {
//          if (!d[head]) tot+=w[head];
            push(i,now.r);
        }
*/          

        //处理 end[i] 显然最多影响到 now.r 
        k--;
    }

    cout<<ans<<'\n';

// 调试 
/*
        while( !q.empty() ){
        cout << q.top().l << ' ' << q.top().r <<' '<< q.top().w << endl;
        q.pop();
    }
    for (int i=1;i<=n;i++) 
    {
        cout<<end[i]<<' ';      
    }

*/  

//  while (1);

}