P8298 [COCI2012-2013#2] POPUST 题解

· · 题解

题目

题目大意

有 N 种饭菜，每种饭菜有两种价格 A_i 和 B_i 。对于两种价格，如果你的选的第一道菜是 i ，则它的价格为 A_i 否则为 B_i ,求对于点 [1,N] 道菜所需的最低价格 。 不管点菜的顺序，不会点两道同样的菜 。

思路

考虑贪心。

zhx说的好，遇事不决先排序 。

因为不管点菜的顺序，所以我们将 B_i 按从小到大的顺序拍一遍序，显然，对于 B_i 较小是更优的。我们可以取出前 k-1 个 B_i 和第 N-k+1 个 A_i 。 即

ans_i \ = \ (\sum_{i=1} ^{k-1}b_i ) + (\min_{i=k}^n a_i)

这样就够了？显然不是。例如这么一组数据

4
1 2 
114514 15
1919810 8
1145141919810 45

如果我们按照上面的方法计算的话，例如当 k=2 时， ans = 3+114514=114517 ,显然我们有更优的解法， ans=1+15=16

也就是说，对于后面的 A_i 的值很大的时候，这样就不够优了 。这时我们就需要取出前 k 个 B_i ，再去掉一个 B_i 选上一个 A_i 。

ans_i \ = \ (\sum_{i=1} ^{k}b_i ) + (\min_{i=1}^{k-1} a_i-b_i)

综合两种情况

ans=min((\sum_{i=1} ^{k-1}b_i ) + (\min_{i=k}^n a_i),(\sum_{i=1} ^{k}b_i ) + (\min_{i=1}^{k-1} a_i-b_i)) 
/* author: Rmax | Always_maxx */
#include<bits/stdc++.h>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long 
#define int long long 
#define bug cout << "I love sport" <<"\n";
#define BYALWAYS_MAXX return 0
using namespace std;
const int N = 1e6+5;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;
inline int read() {
    int x=0,f=0;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) f|=(ch=='-');
    for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch&15);
    return f ? -x : x;
}

struct rmax{
    int a,b;
}food[N];
int n,ans[N];//ans 为答案数组 
int sum[N],mina[N],cha[N];// sum 为 b[i] 的前缀和，mina 为 a[i] 的最小值，cha 为 a[i]-b[i] 的最小值 
inline bool cmp(rmax x,rmax y){
    return x.b < y.b ;//排序 
}

inline void init()
{
    n=read();
    for(int i=1;i<=n;i++) food[i].a=read(),food[i].b=read();//读入 
    sort(food+1,food+n+1,cmp);//按 b 排序 
    cha[0] = INF; 
    memset(mina,INF,sizeof(mina));//预处理 mina 数组 
    for(int i=1;i<=n;i++)
    {
        sum[i] = sum[i-1]+food[i].b;//前缀和数组 
        cha[i] = min(cha[i-1],food[i].a-food[i].b);//求最小差值 
    }
    for(int i=n;i;i--) 
        mina[i] = min(mina[i+1],food[i].a);//反向处理 
    for(int i=1;i<=n;i++)
        ans[i] = min(sum[i-1]+mina[i],sum[i]+cha[i-1]);//求最小值 
} 

signed main()
{
    init();
    for(int i=1;i<=n;i++)
        printf("%lld\n",ans[i]);//只负责输出的主函数 
    BYALWAYS_MAXX;
}

思路来源为这位 int 家族的 dalao