题解：P8298 [COCI 2012/2013 #2] POPUST

· · 题解

题意简述

有 n 道菜，每道菜有作为第一个被点的菜的价格 a 和原来的价格 b，对于每个 k \space(1\le k\le n) 算出点这些菜最少需要的代价。

思路

可以先考虑没有第一道菜的限制时怎么做。
显然是按照 b 排序然后取前缀和。

然后加上这个限制，考虑从原来的思路上去做修改。

这里就可以分为两种情况：从前 k 个选第一个或者从后 n-k 个中选第一个。

首先看第一种：我们选出一个数作为第一个对答案产生的贡献是 a-b，取最小的加上就是最终答案。
第二种情况，我们取前 k-1 个 b，再在后面找出最小的 a，求和即答案。

最后给两种情况取最小值。

代码

#include <bits/stdc++.h>
using namespace std;
#define debug cerr<<"The code runs successfully.\n";
#define endl '\n'
#define TRACE 1
#define tcout TRACE && cout
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define fir first
#define sec second
const int P = 998244353; 
const int Base = 33331;
#ifdef int
const int INF = 0x3f3f3f3f3f3f3f3f; 
#else
const int INF = 0x3f3f3f3f;
#endif
const int N = 5e5 + 10, M = 1e6 + 10;
struct Node {
    int a,b;
}a[N];
inline bool cmp(Node x,Node y) {
    return x.b<y.b;
}
int n,sb[N],qzab[N],hza[N];
//sb是b的前缀和 qzab是a-b的前缀最小值 hza是a的后缀最小值
signed main() {
    fst;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i].a>>a[i].b;
    }
    sort(a+1,a+1+n,cmp);//排序
    //预处理部分
    qzab[0]=INF;
    for(int i=1;i<=n;i++) {
        sb[i]=sb[i-1]+a[i].b;
        qzab[i]=min(qzab[i-1],a[i].a-a[i].b);
    }
    hza[n+1]=INF;
    for(int i=n;i>=1;i--) {
        hza[i]=min(hza[i+1],a[i].a);
    }
    //---
    for(int i=1;i<=n;i++) {
        int x=sb[i]+qzab[i],y=sb[i-1]+hza[i];
        //x是第一种 y是第二种
        cout<<min(x,y)<<endl;//取最小输出
    }
    return 0;
}