本文主要是介绍简单贪心-CodeForces 808C-Tea Party，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
-
简单贪心-CodeForces 808C-Tea Party
题目链接：C. Tea Party
思路：
题目大意是有n个杯子，每个杯子容量为ai，一壶茶容量s，问给定情况是否让所有客人满意
1.每个杯子至少有一半容量的茶，且为整数
2.所有的茶必须倒完
3.满足两个杯子i，j，如果ai>aj，那么i杯中的茶不能少于j杯中的茶
先往每个杯子倒至少一半容量的茶，如果总茶水容量不足以满足每杯至少一半，不符合情况
然后把剩余的茶，依次倒满到容量从大到小的杯子中，这样一定可以满足容量大的杯子倒的茶多，如果杯子全满但茶没倒完，也是不符合要求的
排序，用结构体做，依次倒满需要打乱原先顺序，结构体中记录下标
代码：
#include<iostream>
#include<algorithm>
using namespace std;
struct Cup{int index; //原先下标int V; //杯子容量int tea_v; //杯子装茶的容量
};
bool Mycmp1(Cup a,Cup b)
{return a.V>b.V;;
}
bool Mycmp2(Cup a,Cup b)
{return a.index<b.index;
}
int main()
{int n,w,Cur;Cup Cup_list[105];cin>>n>>w;for(int i=0;i<n;i++){cin>>Cup_list[i].V;Cup_list[i].index=i;if(Cup_list[i].V%2)Cup_list[i].tea_v=Cup_list[i].V/2+1;elseCup_list[i].tea_v=Cup_list[i].V/2;w-=Cup_list[i].tea_v;// cout<<w<<endl;}if(w<0) //不够每杯倒一半，不符合{cout<<"-1"<<endl;return 0;}sort(Cup_list,Cup_list+n,Mycmp1); //对杯子容量降序拍for(int i=0;i<n;i++){if(w==0) //不够倒直接跳出break;Cup_list[i].tea_v+=w; //差取，假设全部茶倒一个杯子，多出杯子容量部分是剩下的茶if(Cup_list[i].tea_v>Cup_list[i].V){w=Cup_list[i].tea_v-Cup_list[i].V; //取多余Cup_list[i].tea_v=Cup_list[i].V; //倒满//cout<<w<<endl;}elsew=0;}if(w) //全部倒满还有剩余{cout<<"-1"<<endl;return 0;}sort(Cup_list,Cup_list+n,Mycmp2); //回复原先顺序for(int i=0;i<n;i++){if(i)cout<<" "<<Cup_list[i].tea_v;elsecout<<Cup_list[i].tea_v;}cout<<endl;return 0;
}
这篇关于简单贪心-CodeForces 808C-Tea Party的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
