[BZOJ2014]&&[Usaco2010 Feb]Chocolate Buying

描述 Description

贝西和其他奶牛们都喜欢巧克力，所以约翰准备买一些送给她们。奶牛巧克力专卖店里有 N 种巧克力，每种巧克力的数量都是无限多的。每头奶牛只喜欢一种巧克力，调查显示，有 Ci 头奶牛喜欢第 i 种巧克力，这种巧克力的售价是 P。

约翰手上有 B 元预算，怎样用这些钱让尽量多的奶牛高兴呢？下面举个例子：假设约翰有 50 元钱，商店里有 S 种巧克力：

                <table>
                    <tbody>
                        <tr>
                            <th > 巧克力品种 </th>
                            <th > 单价 </th>
                            <th > 高兴的奶牛数量 </th>
                        </tr>
                        <tr>
                            <td>1</td>
                            <td>5</td>
                            <td>3</td>
                        </tr>
                        <tr>
                            <td>2</td>
                            <td>1</td>
                            <td>1</td>
                        </tr>
                        <tr>
                            <td>3</td>
                            <td>10</td>
                            <td>4</td>
                        </tr>
                        <tr>
                            <td>4</td>
                            <td>7</td>
                            <td>2</td>
                        </tr>
                        <tr>
                            <td>5</td>
                            <td>60</td>
                            <td>1</td>
                        </tr>
                    </tbody>
                </table>

显然约翰不会去买第五种巧克力，因为他钱不够，不过即使它降价到 50，也不该选择它，因为这样只会让一头奶牛高兴，实在太浪费了。最好的买法是：第二种买 1 块，第一种买 3 块，第四种买 2 块，第三种买 2 块，正好用完 50 元，可以让 1+3+2+2=8 头牛高兴。

输入格式 InputFormat

第一行：两个用空格分开的整数：N 和 B，1<=N≤100000，1≤B≤10^18。

第二行到 N+1 行：第 i+l 行，是两个用空格分开的整数：Pj 和 Ci，1≤Pi，Ci≤10^18。

输出格式 OutputFormat

第一行：一个整数，表示最多可以让几头奶牛高兴。

样例输入 SampleInput

10 255
64 8
26 9
100 10
67 5
25 9
3 2
68 6
71 7
85 2
58 9

样例输出 SampleOutput

11

来源 Source

Silver

BZOJ 2014

代码 Code

按单价排序后贪心。注意数据范围要开 long long.

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
const int inf=0x7fffffff/11.27;
ll i,j,t,n,m,l,r,k,z,y,x;
inline void read(ll &x)
{
    x=0;char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
struct choc
{
    ll pri,num;
    bool operator < (const choc &temp) const
    {
        return (pri<temp.pri);
    }
}c[100005];
ll b,ans;
int main()
{
    read(n);read(b);
    for (i=1;i<=n;i++) read(c[i].pri),read(c[i].num);
    sort(c+1,c+n+1);
    ans=0;
    for (i=1;i<=n;i++)
    {
        t=min(b/c[i].pri,c[i].num);
        b-=t*c[i].pri;
        ans+=t;
    }
    printf("%lld",ans);
    return 0;
}