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

zpy12345 · 2026-03-05 18:12:59 · 题解

[COCI 2012/2013 #2] POPUST

让我来水一发题解！

安利一下我的博客。

思路

我们先将 A 数组和 B 数组从小到大排序。

我们钦定点的第一道菜的编号为 x，那么后面点的菜肯定是 B 数组中前 k 小的，如果前 k 小的中有 x 则替换成第 k+1 小的。

我们对于 x 的取值分类讨论

我们记最小的满足 B_x 不在 B 数组的前 k 项的 x 为 now。

两种情况的答案取较小值即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,A[N],B[N],min1=1e9+5;
struct js
{
    int x,id;
}a[N],b[N];
bool cmp(js x,js y){
    return x.x<y.x;
}
bool bj[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    long long sum=0;
    for(int i=1;i<=n;i++)
    {
        cin>>A[i]>>B[i];
        a[i].x=A[i],b[i].x=B[i],a[i].id=b[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    sort(b+1,b+1+n,cmp);
    int now=1;
    for(int i=1;i<=n;i++)
    {
        if(i!=1) bj[b[i-1].id]=1,sum+=b[i-1].x;
        while(bj[a[now].id]) min1=min(min1,-B[a[now].id]+a[now].x),now++; 
        cout<<min(sum+a[now].x,min1+b[i].x+sum)<<"\n";
    }
    return 0;
}