C - Knapsack

  • Quiz
  • AC
  • 解説
    • 各荷物1つで条件を満たすかチェックする
    • 満たさなかった場合、荷物の重さは floor(W/2)より小さいか、Wより大きいものしかない
    • floor(W/2)より小さい荷物を貪欲に足していってもWを突然超えることはないので、貪欲に足していって条件を満たすか確認すればよい
  • ポイント
    • 各要素を単体チェックすることで、入力の値域を絞れる
void solve(){
  ll N,C;
  cin>>N>>C;
  debug(N,C);
  ll left = (C+1)/2; // 下限

  VI A(N);
  rep(i, N){
    cin >> A[i];
  }
  if(MIN(A)>C){
    // 容量が小さすぎる場合
    // どうやったって無理
    p(-1);return;
  }

  {
    ll sum = SUM(A);
    if(sum<left){
      // 全部足しても下限に届かないなら無理
      p(-1);return;
    }
  }

  rep(i,N){
    ll w = A[i];
    if(left<=w && w<=C){
      // これ1つでいいじゃん
      p(1);
      p(i+1);
      return;
    }
  }

  // それがないということは、各荷物はleft未満、またはCより大きい
  // Cより大きいものは当然採用しない
  // left未満のものは貪欲に足していってもCを超えることはない
  VI Ans;
  ll sum=0;
  rep(i,N){
    if(A[i]>C)continue;
    sum += A[i];
    Ans.push_back(i);
    if(left<=sum && sum<=C){
      // 条件を満たした
      p(SZ(Ans));
      print_vector(Ans);
      return;
    }
  }
  p(-1);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;
    
    while(N--)solve();
    
    return 0;
}