简单贪心-CodeForces 808C-Tea Party-蒲公英云

简单贪心-CodeForces 808C-Tea Party

心已赠人 2022-05-16 06:38 267阅读 0赞

简单贪心-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;
        else
            Cup_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;
        }
        else
            w=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;
        else
            cout<<Cup_list[i].tea_v;
    }
    cout<<endl;
    return 0;
}