Educational Codeforces Round 21 C. Tea Party
贪心
题目描述: 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。逻辑确实没错误，只不过出个细节错误。
字节跳动公司氛围 556人发布