#576. 【提高】买衣服 – 贪心

http://xx.ncyzedu.cn:8007/p/576

买衣服

题目描述

小Ｘ来到了非主流服装店，他看上了 n 件衣服，每一件衣服价格为 Pi，小Ｘ现在手中共有 m 个单位的现金，以及 k 张优惠卷。小Ｘ可以在购买某件衣服时，使用至多一张优惠券，若使用优惠券，则该衣服的价格会下降至 Qi，小Ｘ想知道他最多可以买几件衣服。

输入格式
第一行包含三个用空格隔开的正整数 n,k,m，依次表示衣服总数和优惠券数量及现金总数。
接下来 n 行每行包含两个整数 Pi,Qi，表示该件衣服的价格和优惠价。数据保证 Pi>=Qi。

输出格式
输出数据仅有一行包含一个整数，表示小 X 最多能购买的衣服数。

输入样例

4 1 7
3 2
2 2
8 1
4 3

输出样例

3

样例解释
一种最优的购买方式是购买1,2,3 号物品，并用优惠券购买物品3，总共花费为3 + 2 + 1 = 6。

数据范围
30%的数据，n<=5，k=1，m<=100
对于另外10%的数据，n<=5，k<=5，m<=100
60%的数据，n<=200，k<=200
80%的数据，n<=2500，k<=2500
100%的数据，n<=50000，k<=50000，m<=10^16

思路
选一个合适的策略，但如何证明该策略的正确性？

策略1：将所有衣服优惠前后都加放入堆中，接下来维护一些信息

• 优惠前后的同一件衣服只能买一次
• 剩余现金
• 剩余优惠卷

策略2：先按优惠后价格从小到大排，买完优惠卷；
再按优惠前价格从小到大排，直到买不起下一件为止

• 策略1 部分 wa

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
typedef long long LL;
int n,k,vis[N];
LL m;

struct T{
    LL p,q; int id;
    bool operator< (const T& t) const{
        return p > t.p;
    }
};
priority_queue<T> qu;

int main(){
    cin>>n>>k>>m;  LL p,q;
    for(int i=1; i<=n; i++){
        cin>>p>>q;
        qu.push({p,q,i}), qu.push({q,-1,i});
    }
    int ans=0;
    while(qu.size()){
        T t=qu.top(); qu.pop();
        if(vis[t.id] || m < t.p) continue;
        if(t.q==-1 && k==0) continue;
        if(t.q==-1) k--;
        vis[t.id]=1, ans++, m -= t.p;
    }
    cout<<ans;
    return 0;
}

• 策略2：AC了

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long LL;
int n,k,vis[N];
LL m;

struct T {
    LL p,q,id;
    bool operator <(const T&t) const{
        return q < t.q;
    }
} t[N];

bool cmp2(T a,T b) {
    return a.p < b.p;
}

int main() {
    cin>>n>>k>>m; LL p,q;
    for(int i=1; i<=n; i++) {
        cin>>p>>q; t[i]= {p,q,i};
    }
    int ans=0;
    sort(t+1, t+1+n);
    for(int i=1; i<=k; i++) {
        if(m < t[i].q) break;
        m -= t[i].q, vis[t[i].id]=1, ans++;
    }
    sort(t+1, t+1+n, cmp2);
    for(int i=1; i<=n; i++) {
        if(vis[t[i].id]) continue;
        if(m < t[i].p) break;
        m -= t[i].p, ans++;
    }
    cout<<ans<<endl;
    return 0;
}