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);

}