观光公交[NOIP2011-Day2T3][贪心]

题目

Luogu
$1\le n\le 1,000,1\le m\le 10,000,0\le k\le 100,000,0\le D_i?\le 1000,0\le T_i\le 100,000$

思路

首先思考，问什么可以贪心？
据说当初考试时，很多人想的 $Dp$ 然后就挂了
这也是出题人和考生玩心理战术
为了更好说明为什么可以贪心，我们记
$f_i$ 为不使用氮气加速到达 $i$ 点时间，
$cn{t}_i$ 为 $i$ 点下车人数，
$Las{t}_i$在 $i$ 点最晚出发时间
则 fi=max{fi?1,Lsti?1}+di?1f_i=max\{f_{i-1},Lst_{i-1}\}+d_{i-1}fi?=max{ fi?1?,Lsti?1?}+di?1?
对发现我们只对 $f_i$,$Las{t}_i$ 的大小关系会影响我们决策
也就是人等车和车等人两种
我们可以进行分类讨论
1.$f_i>Las{t}_i$(人等车)
由于它加速后也会影响到后一段，所以可以暴力找出在它后面连续的一段 $f_j>Las{t}_j$
在这些位置下车的人都会提前 $1$ 单位时间下车
2.$f_i<=Las{t}_i$(车等人)
此时并不会对 $i$ 后面的产生影响，只会影响这 $cn{t}_i$ 个人
综上我们每次只需要这样一段就行了：

影响的人数是这一段下车人数之和
问题来了，为什么可以贪心？
口胡一下(因为贪心本身就不好说)
因为每一段有 $D_i$ 的限制
假设现在你就取包含这一段最大的区间 $D_i$ 又恰好是最小的
你早取晚取都会把 $D_i$ 取完，然后就裂成了两段
假设不取 $D_i$ 没有取 $D_i$ 优
每次取最大的影响人数
觉得应该可以从 $Dp$ 决策最优来讲，但是懒，不会

代码

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<vector>
#include<ctime>
#include<bitset>
#include<cmath>
#include<cstdio>
#include<climits>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define ULL unsigned long long
int read(){
    bool f=0;int x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define MAXN 100000
#define INF 0x3f3f3f3f
int d[MAXN+5],Last[MAXN+5],cnt[MAXN+5],f[MAXN+5];
int Max(int a,int b){
    return a>b?a:b;}
int T[MAXN+5],A[MAXN+5],B[MAXN+5];
int main(){
    //f[i]:到达 i 实际时间 int n=read(),m=read(),k=read();for(int i=1;i<n;i++)d[i]=read();for(int i=1;i<=m;i++){
    T[i]=read(),A[i]=read(),B[i]=read();Last[A[i]]=Max(Last[A[i]],T[i]);cnt[B[i]]++;}f[1]=0;for(int i=2;i<=n;i++)f[i]=Max(f[i-1],Last[i-1])+d[i-1];while(k--){
    int Maxnum=0,L=0,R=0;for(int i=2;i<=n;i++){
    if(d[i-1]==0) continue;int tmp=0,p1=i,p2=n;for(int j=i;j<=n;j++){
    tmp+=cnt[j];if(f[j]<=Last[j]){
    p2=j;break;}}if(tmp>Maxnum)Maxnum=tmp,L=p1,R=p2;}if(!Maxnum) break;d[L-1]--;for(int i=L;i<=R;i++)f[i]--;}int ans=0;for(int i=1;i<=m;i++)ans+=f[B[i]]-T[i];printf("%d\n",ans);return 0;
}

思考

多积累对贪心题的认知