Codeforces 853B Jury Meeting (差分+前缀和)

题目大意：

有$ n（n<=1e5）$个城市和一个首都（0号城市），现在每个城市有一个人，总共有$ m (m<=1e5)$次航班，每个航班要么从首都起飞，要么飞到首都去。每个飞机当天飞当天到。且坐飞机这一天什么也不能干，只能等飞机。每个飞机有一个花费和起飞时间。现在要把所有人集中到首都$ k(k<=1e6) $天，然后让他们各自回家。求最小花费，如果不可能实现k天或者不能回家了。或者去不了首都等等都输出-1。

解题分析：

首先判断是否有至少长度为k的区间能够保证所有人能够来，并且回去。之后再利用差分、前缀和维护一定区间内所有人能够出发和到达的最小花费。

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

#define mp make_pair

#define fi first

#define se second

const int N = 1e6+;

typedef long long ll;

typedef pair<int,int> paii;

vector<paii> G[N],G1[N];

const ll INF = 1e15;

ll preday[N],lastday[N];

int n,m,k;

bool cmp1(paii a,paii b){ return a.fi==b.fi?(a.se<b.se):(a.fi<b.fi); }

bool cmp2(paii a,paii b){ return a.fi==b.fi?(a.se<b.se):(a.fi>b.fi); }   //优先回来时间晚，花费少的航班

int main(){

    scanf("%d%d%d",&n,&m,&k);

    for(int i=;i<=m;i++){

        int day,u,v,cost;scanf("%d%d%d%d",&day,&u,&v,&cost);

        if(!v)G[u].pb(mp(day,cost));    //每个人出发的航班

        if(!u)G1[v].pb(mp(day,cost));   //每个人回来的航班

    }

    int l=-,r=1e9;   //记录能够让所有人聚集在一起的最大区间长度

    for(int i=;i<=n;i++){

        sort(G[i].begin(),G[i].end(),cmp1);

        sort(G1[i].begin(),G1[i].end(),cmp2);

        if(G[i].size())l=max(l,G[i][].fi+);

        if(G1[i].size())r=min(G1[i][].fi-,r);

        if(G[i].size()== || G1[i].size()==)return *puts("-1");   //如果这个人不能出发或者回来

    }

    if(r-l+<k || l==- || r==1e9)return *puts("-1");

    for(int i=;i<=n;i++){

        ll now=INF;

        preday[]+=now;

        for(int j=;j<G[i].size();j++){   //从出发时间早的方案开始遍历。前缀求和之后，相当于只保留了(最早)的(最便宜)的方案的值

            if(G[i][j].se<now){

                preday[G[i][j].fi]-=now;

                preday[G[i][j].fi]+=G[i][j].se;

                now=G[i][j].se;

            }

        }//这里如果求前缀的话，sum_preday[day]就相当于得到第i个人在1~day天内出发所花费的最少钱数

        now=INF;

        lastday[int(1e6)]+=now;

        for(int j=;j<G1[i].size();j++){

            if(G1[i][j].se<now){

                lastday[G1[i][j].fi]-=now;

                lastday[G1[i][j].fi]+=G1[i][j].se;

                now=G1[i][j].se;

            }

        }//这里如果求后缀，sum_lastday[day]就相当于得到第i个人day~1e6天内回来所花费的最少钱数

    }

    //计算1~n次之后，sum_preday[day]就表示n个人，在1~day天能够出发的最少钱数(如果他在day天之前能够出发的话，不能出发的话，他的前缀花费为INF)

    //后缀sum_lastday[day]同理

    for(int i=;i<=int(1e6);i++)preday[i]+=preday[i-];    //计算前缀

    for(int i=int(1e6);i>=;i--)lastday[i]+=lastday[i+];  //计算后缀

    ll ans=INF;

    for(int i=l;i+k-<=r;i++)

        ans=min(ans,preday[i-]+lastday[i+k]);

    printf("%lld\n",ans);

}

2019-03-02