简单贪心-CodeForces 808C-Tea Party

心已赠人 2022-05-16 06:38 137阅读 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;
    }

[C. Tea Party]: http://codeforces.com/problemset/problem/808/C