公式

B - お菓子選びコンテスト / Candy Selection Contest 解説 by physics0523


問題文を読むと、 \(T_i+C_i\) が大きい方からお菓子を選ぶことが最善であることがわかります。
よって、 \(N\) 個の \(T_i+C_i\) の値を降順(大きい方から順)にソートして先頭 \(K\) 個の値の合計を答えればよいです。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N,K;
  cin >> N >> K;
  vector<ll> pt(N);
  for(ll i=0;i<N;i++){
    ll T,C;
    cin >> T >> C;
    pt[i]=T+C;
  }
  sort(pt.rbegin(),pt.rend());
  ll res=0;
  for(ll i=0;i<K;i++){ res+=pt[i]; }
  cout << res << "\n";
  return 0;
}

投稿日時:
最終更新: