经典的贪心问题

题目说：

商店里有n中饮料，第i种饮料有mi毫升，价格为wi。

小明现在手里有x元，他想吃尽量多的饮料，于是向你寻求帮助，怎么样买才能吃的最多。

请注意，每一种饮料都可以只买一部分。

输入输出格式

输入描述:

有多组测试数据。
第一行输入两个非负整数x和n。
接下来n行，每行输入两个整数，分别为mi和wi。
所有数据都不大于1000。
x和n都为-1时程序结束。

输出描述:

请输出小明最多能喝到多少毫升的饮料，结果保留三位小数。

这道题呢读懂题意后第一想法就是先买完性价比最高的，然后依次买次高，直到最低（不管钱有没有中途花完都按照这个顺序去花）

这个花的顺序也就是wi/mi（单位：元/毫升）由小到大的排列顺序，所以我们用到c++的一个函数：sort，这个函数我查了一下，可以传两个或三个变量，这里特意记了一下：

参数1：第一个参数是数组的首地址，一般是数组名或者迭代器。

参数2：要排序数据的尾地址。

参数3：默认可以不填，如果不填sort会默认按数组升序排序。可以自定义一个排序函数，改排序方式为降序。（不填的话只能用于基本的数字排序，想排结构体中的某个数据的话就得自己定义一个cmp作为sort第三个参数）

这里解决之后呢就把题目抽象为一个贪心算法的模型，只顾眼下，也就是局部的最优解，和咱们前面提到的? 买光现存最便宜的那种饮料，是同一个思路

后面就是比较常规的自然而然的思路啦，我在注释里标一下也方便自己日后回忆

#include<bits/stdc++.h>
using namespace std;
struct Node{
?? ?double mi,wi;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //这里要定义成double，虽然题目中说这俩输入的是int
}a[10];? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???????????????????但是后续的数据都是double，保险起见
bool cmp(struct Node a,struct Node b){? ? ? ? ? ? ?（float就不行，可能因为有效位只有7位） ? ? ?
?? ?return a.wi/a.mi<b.wi/b.mi;? ? ? ? ? ? ? ? ? ? ? ? //这就是cmp函数，sort的第三个参数，这种就是升序
}
int main(){
?? ?int x,n;
?? ?while(scanf("%d %d",&x,&n)!=EOF){
?? ??? ?if(x==-1&&n==-1) break;
?? ??? ?for(int i=0;i<n;i++)
?? ??? ??? ?scanf("%lf %lf",&a[i].mi,&a[i].wi);
?? ??? ?sort(a,a+n,cmp);? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //第一个参数是数组起始数据，第二个是第n+1个数据
?? ??? ?double hedao=0;????????????????????????????????????????
?? ??? ?for(int i=0;i<n;i++){
?? ??? ??? ?if(x>=a[i].wi){? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//如果现在还买得起a[n]款水，就买光
?? ??? ??? ??? ?hedao+=a[i].mi;
?? ??? ??? ??? ?x-=a[i].wi;
?? ??? ??? ?}
?? ??? ??? ?else{
?? ??? ??? ??? ?hedao+=x*a[i].mi/a[i].wi;? ? ? ? ? ? ?//如果已经买不起了，就买一部分，按目前剩的钱/单价
?? ??? ??? ??? ?break;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 同时停止继续循环，因为买完这款就彻底没钱了
?? ??? ??? ?}
?? ??? ?}
?? ?printf("%.3lf\n",hedao);
?? ?}
?? ?return 0;
}