思路就是从小到大排序然后一个个累加,如果到一个地方了大于了 W 就看这个数是否在范围内,不在就无解在就输出这个;否则如果到一个地方之后在范围内,那么从前往后输出到当前位置。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
const int N=200085;
struct node
{
ll w,id;
}a[N];
bool cmp(node x,node y){return x.w<y.w;}
ll W,T,n,s[N],l;
int main()
{
T=read();
while(T--)
{
n=read(),W=read(),l=0;
for(int i=1;i<=n;i++)
a[i].w=read(),a[i].id=i;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
s[i]=s[i-1]+a[i].w;
while(++l&&s[l]<(W+1>>1)&&l<=n);
if(s[l]>W)
{
if(a[l].w>W)printf("-1");
else printf("1\n%lld",a[l].id);
}
else
{
printf("%lld\n",l);
for(int i=1;i<=l;i++)
printf("%lld ",a[i].id);
}
printf("\n");
}
return 0;
}
第二个点一直WA……