Codeforces 1446A. Codeforces Round #683 (Div. 1, by Meet IT) A(思维)
原题链接
简单
作者:
小小_88
,
2022-12-08 00:36:17
,
所有人可见
,
阅读 191
Knapsack
C++ 代码
/*
本题要将选一些物品使得价值和在 [(m + 1) / 2, m] 之间
首先对于价值 > m 的物品直接忽略。
剩下的物品中如果存在价值 >= (m + 1) / 2 的物品,则这一个物品就是答案。
否则说明剩下的所有物品的价值都是 < (m + 1) / 2 的,因此可以从大到小(从小到大)累加所有物品,当价值和
>= (m + 1) / 2 时就可以输出方案了,如果累加了所有物品价值还是 < (m + 1) / 2,则无解。
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PLI;
const int N = 200010;
int n;
LL m;
PLI a[N];
void check()
{
int i;
for(i = n; i >= 1; i--)
{
if(a[i].first > m) continue; //跳过所有 > m 的物品
else if(a[i].first >= (m + 1) / 2) //遇到符合条件的物品直接就是答案
{
printf("%d\n%d\n", 1, a[i].second);
return;
}
break;
}
//到这说明需要从小于 (m + 1) / 2 的物品中累加出结果
n = i;
LL res = 0;
int idx = 0;
for(i = 1; i <= n; i++)
{
if(res + a[i].first > m) break;
res += a[i].first;
idx++;
}
if(res < (m + 1) / 2) //如果剩下所有物品累加都不满足条件,则无解
{
puts("-1");
return;
}
//否则输出方案
printf("%d\n", idx);
for(int i = 1; i <= idx; i++) printf("%d ", a[i].second);
puts("");
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%lld", &n, &m);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i].first);
for(int i = 1; i <= n; i++) a[i].second = i;
sort(a + 1, a + 1 + n); //将所有物品按价值从小到大排序
check();
}
return 0;
}