描述
题解
这道题是贪心问题,分为两种情况贪心:
第一种是选取的盒子左边界之和≥X;
第二种是C-没有选取的盒子的右边界之和≥X,即C-N个盒子右边界之和+选取的盒子右边界之和≥X。
所以,分别按照左边界和右边界进行从大到小排序,逐个选取,获取两个结果,从这两个结果中取最优即可。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 55;
struct dessert
{
int low;
int high;
} Dessert[MAXN];
bool cmpA(dessert a, dessert b)
{
return a.low > b.low;
}
bool cmpB(dessert a, dessert b)
{
return a.high > b.high;
}
int main(int argc, const char * argv[])
{
int T;
cin >> T;
while (T--)
{
int N, C, X;
cin >> N >> C >> X;
long long sum = 0;
for (int i = 0; i < N; i++)
{
cin >> Dessert[i].low >> Dessert[i].high;
sum += Dessert[i].high;
}
int posA = 0, posB = 0;
long long resA = 0;
long long resB = C - sum;
sort(Dessert, Dessert + N, cmpA);
while (resA < X)
{
resA += Dessert[posA++].low;
}
sort(Dessert, Dessert + N, cmpB);
while (resB < X)
{
resB += Dessert[posB++].high;
}
if (posA < posB)
{
cout << posA << '\n';
}
else
{
cout << posB << '\n';
}
}
return 0;
}