P2240 【深基12.例1】部分背包问题

思路：金币可以随意分割，先装单价最高的金币 2.证明贪心的有效性 3.用反证法，假设不装单位价值为6的金币装单位价格为5的金币

输入：

4 50
10 60
20 100
30 120
15 45

输出

240.00

//1.输入n堆金币，，用结构体 
//2.对金币的单位价值从小到大排序
//3。对排序后的金币：从第一对开始装，直到装不下为止，记录装入金币的总价
//4.输出总价值 
#include<bits/stdc++.h>
using namespace std;
struct coin{
    int m,v;//重量，价值 
    double avg;//单位价值 

}cs[105];
bool cmp(coin c1,coin c2){//排序规则 
	return c1.avg>c2.avg;
}
int main(){
	int n,t,mark=0;//mark标记 (装的次数) 
	double ans=0;//总价值 
	cin>>n>>t;//n空间/重量，t价值 
	for(int i=0;i<n;i++){
		cin>>cs[i].m>>cs[i].v;//循环输入样例 
		cs[i].avg=1.0*cs[i].v/cs[i].m;//得到单位价值 
		
	}
	sort(cs,cs+n,cmp);//将单位值从大到小排序 
	while(t>=cs[mark].m && mark<n)//背包剩余的空间大于或者等于，装的次数少于件数 
	{
		t-=cs[mark].m;//背包剩余可以装的重量/空间 
		ans+=cs[mark].v;//总价值 
		mark++;
	}	
	ans+=t*cs[mark].avg;//如果背包装不下完整的金币就得进行切割（剩余的背包重量乘于单价） 
	printf("%.2f",ans);
    
	return 0;
} 

P1223 排队接水

输入

10 
56 12 1 99 1000 234 33 55 99 812

输出

3 2 7 8 1 4 9 6 10 5
291.90