Educational Codeforces Round 21 C. Tea Party

贪心

题目链接 http://codeforces.com/contest/808/problem/C

题目描述: Polycarp招待朋友，给朋友们倒茶，朋友们的茶杯容量不一样，Polycarp的茶壶容量是w，w小于朋友茶杯满容量的总和。倒茶时需要满足几个条件。

1.每个人的茶杯必须至少倒一半。

2.每个人的茶杯倒整数的容量。

3.如果甲茶杯的容量大于乙茶杯的容量，那么甲茶杯里的茶不能少于乙。

4.Polycarp茶壶里的茶必须倒光。

题目分析：

比较水的一个贪心题，先对茶杯容量排一个序，按照从小大大排序，遍历每个茶杯，此时每个茶杯都正好倒一半的茶（因为至少要满足每个朋友都有茶），如果遍历完w还>0，从后往前倒满遍历。最后判断输出即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <vector>
using namespace std;

const int maxn=100+10;
struct person
{
    int v,index;
    person(int a,int b):v(a),index(b) {}
    person() {}
};

bool cmp (const person a,const person b)
{
    return a.v<b.v;
}
person cup[maxn];

int main()
{
    int n,w,mmin=999999,mmax=-1;
    cin >> n >> w;
    for(int i=0; i<n; i++)
    {
        scanf("%d",&cup[i].v);
        cup[i].index=i;
    }
    sort(cup,cup+n,cmp);
    vector< pair<int,int> > outp;
    for(int i=0; i<n; i++)
    {
        if(w>=((cup[i].v+1)/2))
                outp.push_back(pair<int,int>(cup[i].index,(cup[i].v+1)/2));
        w-=(cup[i].v+1)/2;
    }
    if(w>0)
    {
        for(int i=n-1; i>=0; i--)
        {
            if(w<=(cup[i].v-outp[i].second))
            {
                outp[i].second+=w;
                w-=w;
            }
            else if(w>(cup[i].v-outp[i].second))
            {
                w-=(cup[i].v-outp[i].second);//WA好几次是因为这两句话顺序写反了
                outp[i].second+=(cup[i].v-outp[i].second);
            }
            if(w<=0) break;
        }
    }
    if(w==0)
    {
        if(outp.size()!=n) cout << "-1";
        else
        {
            sort(outp.begin(),outp.end());
            for(int i=0; i<n; i++)
            {
                cout << " " << outp[i].second;
            }
        }
    }
    else cout << "-1";
    return 0;
}

还是需要严谨，对于每句语句的顺序要仔细考虑，下一句话是否会用的上一句话的变量，使用到改变之前的变量值还是改变之后的变量值，这点尤为重要。有时候自己想法是正确的，但写的程序和想法不一，你还认为自己的逻辑没有错误，就会很难debug。逻辑确实没错误，只不过出个细节错误。