P3045 [USACO12FEB]牛券Cow Coupons

题目描述

Farmer John needs new cows! There are N cows for sale (1 <= N <= 50,000), and FJ has to spend no more than his budget of M units of money (1 <= M <= 10^14). Cow i costs P_i money (1 <= P_i <= 10^9), but FJ has K coupons (1 <= K <= N), and when he uses a coupon on cow i, the cow costs C_i instead (1 <= C_i <= P_i). FJ can only use one coupon per cow, of course.

What is the maximum number of cows FJ can afford?

FJ准备买一些新奶牛，市场上有N头奶牛(1<=N<=50000)，第i头奶牛价格为Pi(1<=Pi<=10^9)。FJ有K张优惠券，使用优惠券购买第i头奶牛时价格会降为Ci(1<=Ci<=Pi)，每头奶牛只能使用一次优惠券。FJ想知道花不超过M(1<=M<=10^14)的钱最多可以买多少奶牛？

输入输出格式

• Line 1: Three space-separated integers: N, K, and M.

• Lines 2..N+1: Line i+1 contains two integers: P_i and C_i.

• Line 1: A single integer, the maximum number of cows FJ can afford.

输入输出样例

4 1 7 
3 2 
2 2 
8 1 
4 3 

3 

说明

FJ has 4 cows, 1 coupon, and a budget of 7.

FJ uses the coupon on cow 3 and buys cows 1, 2, and 3, for a total cost of 3 + 2 + 1 = 6.

分析：其实很容易发现这就是一道背包题，对于每头牛我们都有用与不用优惠券两种选择，然而会发现，这个m不是一般的大，所以不能用dp.dp和贪心是差不多的，考虑到dp不行，试试贪心。因为我们的目标是要使买的牛最多，也就是花的钱最少，于是我当时想了一种贪心：我们可以取前k个用优惠券的价格（从小到大排序），然后和不排序的放在一起排序一下，然后遍历求解.这样的话有一个问题：我们已经假定前k个用优惠券的牛用优惠券，然而有时候不用优惠券比用优惠券要好，那就是用不用价格都相等的情况，所以我们不再取前k个，我们把每头牛拆成2头牛，一头用优惠券，一头不用，然后排序求解即可.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

int n, k,p[50010],c[50010],vis[50010],ans;
long long m;

struct node
{
    int id, use, money;
}e[100010];

bool cmp(node a, node b)
{
    if (a.money == b.money)
        return a.use < b.use;
    return a.money < b.money;
}

int main()
{
    scanf("%d%d%lld", &n, &k, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &p[i], &c[i]);
        e[i * 2 - 1].id = i;
        e[i * 2 - 1].use = 1;
        e[i * 2 - 1].money = c[i];

        e[i * 2].id = i;
        e[i * 2].use = 0;
        e[i * 2].money = p[i];
    }
    sort(e + 1, e + n * 2 + 1, cmp);
    for (int i = 1; i <= n * 2; i++)
    {
        if (vis[e[i].id])
            continue;
        if (e[i].use && k <= 0)
            continue;
        if (m <= 0)
            break;
        if (m >= e[i].money)
        {
            vis[e[i].id] = 1;
            ans++;
            m -= e[i].money;
            if (e[i].use)
                k--;
        }
    }

    printf("%d", ans);
    return 0;
}