常州买衣服

时间限制: 1 Sec  内存限制: 128 MB

题目描述

不知道是拔河训练的作用还是那个梦的缘故，反正小Ｘ是一天天瘦下来了，虽然还没有中天学长那么帅，但比起 Q 老师已经瘦了很多，小Ｘ原先买的衣服都嫌大了，于是他想去买些新衣服，小Ｘ的衣服原先一直是在非主流服装店买的，他的衣服一般店里是买不到的，而去非主流服装店肯定能买到，如膝盖上挖了两个洞的牛仔裤，正常人穿了像雨衣的冲锋衣等应有尽有，并且每买一件就送一张优惠券，小Ｘ这些年下来积聚了好多张优惠券，这次非主流服装店恰好举行优惠活动，用优惠券购买衣服可享受优惠价！
小Ｘ来到了非主流服装店，他看上了 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

 

提示

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.是否钱还够

                   3.选了打折的衣服就不能再选同一件没打折的衣服。

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n, k, vis[50005];
LL m;

struct node
{
	LL p, w;
	int id;
	bool operator <(const node &x)const{
		return p > x.p;
	}
}a[50005];

priority_queue<node> q;

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d %d %lld", &n, &k, &m);
	for (int i = 1; i <= n; i++){
		scanf("%lld %lld", &a[i].p, &a[i].w);
		a[i].id = i;
		q.push(a[i]);
	}
	node t;
	for (int i = 1; i <= n; i++){
		t.p = a[i].w, t.w = -1, t.id = a[i].id;
		q.push(t);
	}
	LL sum = 0;
	int ans = 0;
	while(q.size()){
		node t = q.top();
		q.pop();
		if(vis[t.id] || (t.w == -1 && !k)) continue;
		if(sum + t.p > m) break;
		ans++, sum += t.p;
		vis[t.id] = 1;
		if(t.w == -1) k--;
	}
	printf("%d\n", ans);

	return 0;
}
/**/