题目描述

新年快到了，笑笑打算给他的好朋友们发贺年卡，而且他已经选好了自己要购买的贺卡的样式。

俗话说得好，货比三家，笑笑来到商店，看了各个商铺这种贺卡的价钱。不仅如此，笑笑还记住了每个商铺的存货量。

已知笑笑打算购买 $m$ 张贺卡，问他最少花多少钱。

输入格式

第一行两个整数 $m$ 和 $n$ 。其中 $m$ 表示要购买的贺卡的数量，$n$ 表示商铺的个数。

以下 $n$ 行，每行两个整数，分别表示该商铺这种贺卡的单价和存货量。

数据规模

$0 \lt m,n \le 50000$

每个商铺贺卡单价在 1~1000 之间，货存量在 1~50 之间

输入保证商铺的总存货量不少于 $m$。

输出格式

仅一个数，表示笑笑买贺卡的最少花费。

样例

10 4
4 3
6 2
8 10
3 6

36

解题思路

我们总是选择最便宜的贺年卡，如果供应量大于我们的需求量，那么就只买需要的那么多；

如果供应量小于我们的需求量，那么就有多少买多少。我们的需求量就响应减少。比方说，这一家是最便宜的，但是只有 10 张卡，我们需要 100 张的，那就先买下这 10 张，需求量就从 100 调整为 90 ，接着找下一个次便宜的。

因此，我们需要对供应信息进行排序，把单价最便宜的排在前面。但是，每一个供应信息都是由供应量和价格构成的，这两个信息构成一个整体，单独对其中一个排序就会出现刻舟求剑的错误：船在走，宝剑呆在原地，最终再都找不会宝剑了。

所以，我们引入结构体。这个结构体包含了价格和供应量信息。以后，对结构体变量进行操作，挪动位置的时候就把价格和供应量一起挪动了。

大多数同学在学习本题的时候都学过结构体排序。我们先假设我们是不会结构体排序的，写出了下面的程序：

#include<bits/stdc++.h>
using namespace std;
struct card
{
    int price,amt;
} x[50001];
int t,n,m,ans;
int main()
{
    scanf("%d%d",&m,&n);

    for(int i=0;i<n;i++)
		scanf("%d %d",&x[i].price,&x[i].amt) ;
     	
	sort(x,x+n);
	
	for(int i=0;i<n&&m>0;i++){
		if(m<=x[i].amt)
		{
			ans += x[i].price*m;
			m = 0; 
		}
		else
		{
			ans += x[i].price*x[i].amt;
			m -= x[i].amt;
		}		
	}
	     
	printf("%d",ans);	

	return 0;
}

编译的时候就会出现下面的错误提示：

我们今天来研究一下这个错误信息。第一个，我们看到 dev cpp 自动打开了一个头文件 (predefined_ops.h)，h 后缀的文件是头文件。头文件就是描述各个函数库文件里面有什么函数的。define 是“定义”的意思，这里用了过去分词（加了ed），表示的形容词磁性，pre 是英语的前缀，就是“提前”的意思，所以 predefined 就是“预定义”的意思，ops 是 operators 的缩写，所以整个单词 predefined_ops 就是 预先定义好的运算符的意思。

然后，高亮度的这一行我们看到了 iterator 这个词，我们学 STL 的时候学过，这是迭代器。再深入的我们就不讲了，否则大家晕。

我们再来看下面 error 提示的英文：[Error] no match for 'operator<' (operand types are 'card' and 'card') ,这句话的意思是，没有匹配到运算符 <，这个运算符应该要有两个参数，两个参数都应该是 card 类型的。card 就是我们程序里面定义的结构体了。

把所有的信息综合起来，这个错误的意思是：dev cpp 编译器在这个预先定义好的操作符里面去找关于 card 结构体的 < 运算符，没找到。

所以，我们过去已经学过自己定义一个 cmp 函数，传递给 sort（第三个参数）

bool cmp(card i, card j){
	return i.price<j.price ;
}

然后，sort的时候是

sort(x,x+n,cmp);

上面的出错提示是说找不到 < (小于比较)运算符。而定义 cmp 函数，把 cmp 传递给 sort 的目的是让 sort 不要去找 < 运算符，直接基于 cmp 来比较两个 card 变量的大小。今天，我们要学习一个新的方法：定义运算符。

我们先来讲述接个关于运算符的概念：

1. 运算符是一种特殊的函数。例如，上面的 cmp 是一个函数，输入参数是两个 card ，返回的是 bool 。两个 int 变量之间的比较其实也是函数

int a=5,b=10;
if(a<b)
	cout<<"a比b小";
else
	cout<<"a并非比b小";

上面这段程序里面 a<b 是一个运算式子，中间的 < 就是运算符，就类似于函数，你可以把 a<b 的运算相乘调用了一个叫 < 的函数，类似这样子：<(a,b)，来到这里，是不是和上面的 cmp 很类似，只不过一个叫 cmp 一个叫 <。

2. 对于基本的数据类型（int,long,char,bool等等），c++ 已经定义好了一些基本的运算符运算法则了。如果你不喜欢，你可以自己写一个来替代默认的那个，这个教重载

3. 对于你自己定义的结构体，很多运算符是没有的。而不带第三个参数的 sort 函数是需要用到 < ，如果你没定义，就会报上面的错误。

所以，下面我们就来学如何定义这个运算符。

定义运算符

对于结构体运算符的定义，有两种方法：

1. 在结构体定义完之后再来定义运算符

这个方法和定义 cmp 几乎一行，只不过 cmp 换成了 <，另外前面增加一个关键词 operator，表示你定义的是运算符（特殊的函数）。

struct card
{
    int price,amt;
} x[50001];
bool operator < (card i, card j){
	return i.price<j.price;
}

2. 定义结构体的时候定义运算符

这种方法更加优雅，更符合面向对象编程的码风，写出来的程序更像大师，更好装逼。

设想一下下面代码

card a,b;
// 然后对 a 和 b 赋值，我们略过这部分代码

if(a<b)
	cout<<"贺卡 a 的价格比贺卡 b 更便宜";
else
	cout<<"贺卡 a 的价格并比贺卡 b 便宜";

上面的 a<b 是 a 去比较 b ，我们拟人化想象，a 是主动的一方，b 是被动的一方。也就是说，主动的 a 变量发起了一个比较运算去比较 b ，这个 b 是整个比较过程的参数。所以，按照这个思维模式，整个比较函数就只剩下 1 个参数了。

struct card
{
    int price,amt;
    bool operator < (card other){
		return price<other.price;
	}
}

上面是定义结构体的 card 的时候，直接定义了它有一个运算符 <，它自己本身（也就是说 if(a<b) 里的 a 就是它自己）不是一个参数，它只需要写运算符后面的那个变量作为参数，我们用 other 来命名（你不喜欢 other 改成别的也行）。

比较的时候，自己的价格直接引用 price，（如果想更像马农，就写成 this->price，this 是自己的指针，这些以后再慢慢说）。所以，就是用自己的 price 和 other 参数的 price 比较了。

用了上面的任何一种方法定义了 card 的 < 运算符之后，再去 sort 的时候就不用写 cmp 了。

sort(x+1,x+1+n);