アルゴ式（beta版）の「ソートアルゴリズム」ソートを活用する問題からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。
Q1. 中央値
/* C++による「ソートアルゴリズム」ソートを活用する問題の解答例 Q1. 中央値 https://algo-method.com/tasks/501 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n; cin>>n; vector<double> a(n); for(int i=0;i<n;i++){ cin>>a[i]; } sort(a.begin(),a.end()); cout<<fixed<<setprecision(2); if(n%2==0){ cout<<(a[n/2-1]+a[n/2])/2<<endl; }else{ cout<<a[n/2]<<endl; } return 0; }
・Q2. X 番目に小さい数
/* C++による「ソートアルゴリズム」ソートを活用する問題の解答例 Q2. X 番目に小さい数 https://algo-method.com/tasks/489 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n,m; cin>>n>>m; vector<long long> a(n),x(m); for(int i=0;i<n;i++){ cin>>a[i]; } for(int i=0;i<m;i++){ cin>>x[i]; } sort(a.begin(),a.end()); for(int i=0;i<m;i++){ cout<<a[x[i]]<<endl; } return 0; }
・Q3. 総和の最大値
/* C++による「ソートアルゴリズム」ソートを活用する問題の解答例 Q3. 総和の最大値 https://algo-method.com/tasks/484 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n,k; cin>>n>>k; vector<int> a(n); long long ans=0; for(int i=0;i<n;i++){ cin>>a[i]; } sort(a.begin(),a.end(),greater<int>()); for(int i=0;i<k;i++){ ans+=a[i]; } cout<<ans<<endl; return 0; }
・Q4. 差の最小値
/* C++による「ソートアルゴリズム」ソートを活用する問題の解答例 Q4. 差の最小値 https://algo-method.com/tasks/490 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n,k; cin>>n>>k; vector<ll> a(n); for(ll i=0;i<n;i++){ cin>>a[i]; } sort(a.begin(),a.end()); ll ans=10000000000; for(int i=0;i<n-k+1;i++){ ans=min(ans,a[i+k-1]-a[i]); } cout<<ans<<endl; return 0; }
・Q5. ごはんを買う
/* C++による「ソートアルゴリズム」ソートを活用する問題の解答例 Q5. ごはんを買う https://algo-method.com/tasks/491 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n,k; cin>>n>>k; vector<pair<ll,ll>> ab(n); for(ll i=0;i<n;i++){ cin>>ab[i].first>>ab[i].second; } sort(ab.begin(),ab.end()); ll num=0,ans=0; for(auto& [a,b] : ab){ ans+=(a*min(k-num,b)); num+=b; if(num>=k){ cout<<ans<<endl; return 0; } } }
・Q6. ダブルブッキング
/* C++による「ソートアルゴリズム」ソートを活用する問題の解答例 Q6. ダブルブッキング https://algo-method.com/tasks/928 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; cin>>n; vector<pair<ll,ll>> vp(n); for(ll i=0;i<n;i++){ ll l,r; cin>>l>>r; vp[i]={l,r}; } sort(vp.begin(),vp.end()); bool tf=true; for(ll i=0;i<n-1;i++){ auto [l0,r0]=vp[i]; auto [l1,r1]=vp[i+1]; if(r0>l1){ tf=false; } } if(tf){ cout<<"Yes"<<endl; }else{ cout<<"No"<<endl; } return 0; }
・Q7. 順位表の並び替え
/* C++による「ソートアルゴリズム」ソートを活用する問題の解答例 Q7. 順位表の並び替え https://algo-method.com/tasks/493 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n; cin>>n; vector<tuple<int,int,int,string>> vt(n); int num=0; for(auto& [math,sum,i,s] : vt){ cin>>s>>math>>sum; sum+=math; math*=-1; i=num++; } sort(vt.begin(),vt.end()); for(auto& [math,sum,i,s] : vt){ cout<<s<<" "<<-math<<" "<<sum+math<<endl; } return 0; }
・Q8. 背の低い順
/* C++による「ソートアルゴリズム」ソートを活用する問題の解答例 Q8. 背の低い順 https://algo-method.com/tasks/929 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n,x; cin>>n>>x; vector<tuple<ll,ll,string>> stu(n); for(ll i=0;i<n;i++){ string s; ll h; cin>>s>>h; stu[i]={h,i,s}; } sort(stu.begin(),stu.end()); for(ll i=0;i<n;i++){ auto[h,j,s]=stu[i]; if(j==x){ cout<<get<2>(stu[i-1])<<endl<<get<2>(stu[i+1])<<endl; } } return 0; }
・Q9. テストの順位
/* C++による「ソートアルゴリズム」ソートを活用する問題の解答例 Q9. テストの順位 https://algo-method.com/tasks/492 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; cin>>n; vector<ll> a(n),b(n); for(ll i=0;i<n;i++){ cin>>a[i]; b[i]=a[i]; } sort(b.begin(),b.end()); b.erase(unique(b.begin(),b.end()),b.end()); for(ll i=0;i<n;i++){ ll ans=b.size()-1 -(lower_bound(b.begin(),b.end(),a[i])-b.begin()); cout<<ans<<endl; } return 0; }
・Q10. 投票結果
/* C++による「ソートアルゴリズム」ソートを活用する問題の解答例 Q10. 投票結果 https://algo-method.com/tasks/502 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n; cin>>n; vector<int> a(n); vector<pair<int,int>> ans(n); for(int i=0;i<n;i++){ cin>>a[i]; ans[a[i]].first--; ans[i].second=i; } sort(ans.rbegin(),ans.rend()); for(int i=n-1;i>=0;i--){ cout<<ans[i].second<<" "<<-ans[i].first<<endl; } return 0; }
設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式（beta版）」です。
algo-method.com
