样例已过,求找错 /kk
查看原帖
样例已过,求找错 /kk
326382
Thomas_Cat楼主2020/11/18 23:00

思路:

  • 从大到小排序
  • 如果有直接是一半的,输出
  • 如果没有就加和,然后判断到哪里可以加完
  • 如果没有答案就在最后用一个 flag 来标记输出 1-1
#include<bits/stdc++.h>
using namespace std;
struct node{
    int a;
    int flag;
    bool b=0;
};
bool cmp(node x,node y){
    return x.a>y.a;
}
int main(){
    int t,sum=0;
    cin>>t;
    while(t--){
        bool c_flag=0,w_flag=0;
        int n,w;
        cin>>n>>w;
        node d[100001];
        for(int i=1;i<=n;i++){
            cin>>d[i].a;
            d[i].flag=i;    
        }
        sort(d+1,d+n+1,cmp);
        for(int i=1;i<=n;i++){
            if(sum>=w/2&&sum<=w){
                c_flag=1;
                break;
            }
            if(d[i].a>w) continue;
            else{
                if(d[i].a>=w/2){
                    cout<<1<<endl;
                    cout<<d[i].flag<<endl;
                    w_flag=1;
                    break;
                }
                else{
                    sum+=d[i].a;
                    d[i].b=1;
                }
            }
        }
        if(sum>=w/2&&sum<=w) c_flag=1;
        if(w_flag==1) continue;
        if(c_flag==0) cout<<-1<<endl;
        else{
            int c_tmp=0,co_tmp[100001]={0};
            for(int i=1;i<=n;i++) if(d[i].b==1) co_tmp[++c_tmp]=d[i].flag;
            sort(co_tmp+1,co_tmp+c_tmp+1);
            for(int i=1;i<=c_tmp;i++) cout<<co_tmp[i]<<' ';
        }
        // for(int i=1;i<=n;i++){
        //     cout<<d[i].a<<' '<<d[i].flag<<' '<<d[i].b<<endl;
        // }
    }
    return 0;
}
2020/11/18 23:00
加载中...