こちらの問題についてです
この問題は、全てのAとCについて、高い順にn個選択するプログラムを書けば良いです
そこで以下のコードを提出しました
c++
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 5 int main(void){ 6 ll n,m; 7 cin>>n>>m; 8 ll a[n]; 9 for(int i=0;i<n;i++)cin>>a[i]; 10 ll b[m],c[m]; 11 vector<pair<ll,ll>>ans; 12 for(int i=0;i<m;i++){ 13 cin>>b[i]>>c[i]; 14 ans.push_back(make_pair(c[i],b[i])); 15 } 16 for(int i=0;i<n;i++){ 17 ans.push_back(make_pair(a[i],1LL)); 18 } 19 sort(ans.begin(),ans.end(),greater<pair<ll,ll>>()); 20 ll res =0; 21 for(ll i=0;i<m+n+11;i++){ 22 res += ans[i].first * ans[i].second; 23 n -= ans[i].second; 24 if(n==0){ 25 break; 26 }else if(n<0){ 27 res+=ans[i].first*n; 28 break; 29 } 30 } 31 32 33 cout<<res<<endl; 34 } 35
Aを個数1のB,Cの組と同等に扱い、pairにして大きい順に選び、最後にとりすぎた分戻すという動作をしています
しかしこのプログラムは不正解扱いで、forループ内を以下のように書き換えたプログラムは正解となりました
c++
1 for(ll i=0;i<m+n+10;i++){ 2 res += ans[i].first * ans[i].second; 3 num += ans[i].second; 4 //n -= ans[i].second; 5 /*if(n<=0){ 6 if(n<0){ 7 res+=ans[i].first*n; 8 } 9 break; 10 }*/ 11 if(num==n){ 12 break; 13 }else if(num>n){ 14 res -= ans[i].first*(num-n); 15 break; 16 } 17 }
本質的には同じことをしていると思うのですが……、上がダメで下ならOKな例が思いつきません
どなたか分かる方いましたら回答お願いします
また、この問題も同じ方法で解けるのですが、こちらの場合は上の方法でも下の方法でも正解になりました なぜでしょうか
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2019/05/31 02:20