ABC127-D Integer Cards
https://gyazo.com/3a1ab39c02cf3c23e4ab04f0ddc051cf
解法
配列Aに加え、枚数制限が$ B_iだけある配列Cの数値が書かれたカードの両方の集合を考える
突き詰めると、この集合からN枚を取り出すようにすればokということになる
最初は上記の解き方が浮かばずソートを組み合わせて解こうとしたが、制約上どうしてもTLEが発生. mapで上手く解くと避けることができた
時間計算量$ O(N)
空間計算量$ O(N)
解くのにかかった時間
1時間程度
code:solution.cpp
using namespace std;
void solve(long long N, long long M, std::vector<long long> A, std::vector<long long> B, std::vector<long long> C){
map<long long, long long> m;
for (int i=0; i<M; i++) {
if (m.count(Ci)) m[Ci] += Bi; }
for (auto a : A) {
}
long long ret = 0;
int n = 0;
for (auto iter=m.rbegin(); iter != m.rend() && n < N; iter++) {
for (int i=0; i<(*iter).second && n < N; i++, n++) ret += (*iter).first;
}
cout << ret << endl;
}
int main(){
long long N;
scanf("%lld",&N);
long long M;
scanf("%lld",&M);
std::vector<long long> A(N);
for(int i = 0 ; i < N ; i++){
}
std::vector<long long> B(M);
std::vector<long long> C(M);
for(int i = 0 ; i < M ; i++){
}
solve(N, M, std::move(A), std::move(B), std::move(C));
return 0;
}