洛谷 P1315 观光公交 —— 贪心

题目：https://www.luogu.org/problemnew/show/P1315

问题是想不明白改动一条边会对后面造成怎样的影响；

实际上影响的会是一段，当某个车站出发时间受其来人牵制时，前面的时间减小就不会起到效果；

所以对于每个车站，求一个 g[i] 表示最远能影响到哪个车站，则修改 i 后面那条边，所有到达点在 i ~ g[i] 的人的时间都缩短1；

每次找一个缩短最大的边，然后重新计算每个车站的实际到达时间和 g[i]，其实就是贪心。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const xn=1005,xm=1e4+5;
int n,m,K,d[xn],f[xn],t[xm],tim[xn],ans,st[xm],ed[xm],s[xn],g[xn];
int rd()
{
  int ret=0,f=1; char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();}
  while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();
  return f?ret:-ret;
}
int main()
{
  n=rd(); m=rd(); K=rd();
  for(int i=1;i<n;i++)d[i]=rd();
  for(int i=1;i<=m;i++)
    {
      t[i]=rd(); st[i]=rd(); ed[i]=rd();
      f[st[i]]=max(f[st[i]],t[i]);
      s[ed[i]]++;
    }
  tim[1]=0;
  for(int i=2;i<=n;i++)tim[i]=max(tim[i-1],f[i-1])+d[i-1],s[i]+=s[i-1];
  for(int i=1;i<=m;i++)ans+=tim[ed[i]]-t[i];
  while(K)
    {
      g[n]=n;
      for(int i=n-1;i;i--)
        {
          if(/*tim[i]+d[i]*/tim[i+1]>f[i+1])g[i]=g[i+1];
          else g[i]=i+1;
        }
      int mx=0,c=0;//0 而非 -1 防止 K 有余而 d<0 时减了 -1 
      for(int i=1;i<n;i++)
        if(s[g[i]]-s[i]>mx&&d[i]>0)mx=s[g[i]]-s[i],c=i;//>0
      ans-=mx; d[c]--;
      for(int i=2;i<=n;i++)tim[i]=max(tim[i-1],f[i-1])+d[i-1];
      K--;
    }
  printf("%d
",ans);
  return 0;
}