题解 #

首先我们要计算在每个城堡通关所需要的最少勇士的数量 ( $req_i$ )，这样我们就能知道在招募之后有多少自由支配的勇士 ( $fr_i$ )。 $req_i$ 这么计算 $req_n = 0, req_i = \max \{ a_{i+1} , req_{i+1} - b_{i+1} \}$ 。 $last_i$ 表示最后一个可以派勇士来守卫城堡 $i$ 的城堡。现在问题就转化成了如何分配勇士来守卫这些城堡。我们用贪心的思路：按照城堡的重要程度来守卫，对于城堡 $i$ ，如果我们能在 $last_i$ 前面找到有空闲的勇士那么我们就可以守护这个城堡。

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define fore(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
#define ford(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define pb push_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
using namespace std;
 
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
	int n,m,k,tot;
    cin>>n>>m>>k;
    tot=k;
    vector<int> a(n+1),b(n+1),last(n+1),fr(n+1),req(n+2);
    vector<pii> c(n+1);
    int flag=0;
    for1(i,n){
        cin>>a[i]>>b[i]>>c[i].F;
        c[i].S=i;
        if(tot<a[i]){
            flag=1;
        }else{
            tot+=b[i];
        }
        last[i]=i;
    }
    forn(i,m){
        int u,v;
        cin>>u>>v;
        last[v]=max(last[v],u);
    }
    if(flag) cout<<-1;
    else{
        for(int i=n;i>=1;i--){
            if(i==n) req[i]=0;
            else req[i]=max(a[i+1],req[i+1]-b[i+1]);
        }
        tot=k;
        for1(i,n){
            tot+=b[i];
            fr[i]=tot-req[i];
            tot=req[i];
        }
        sort(c.begin()+1,c.end(),[](pii a,pii b){
            return a.F>b.F;
        });
        int ans=0;
        for1(i,n){
            int val=c[i].F,x=c[i].S;
            int y=last[x];
            while(!fr[y]&&y>0)y--;
            if(y==0)continue;
            fr[y]--;
            ans+=val; 
        }
        cout<<ans;
    }
    return 0;
}

Codeforces 1271D - Portals 题解

题解 #

Code #