CF 798 D - Mike and distribution
問題
問題概要
長さの数列とが与えられる。
いま、数列のindexを個選ぶことが出来る。選んだ個のindexをとするとき、次の条件を満たすように個のindexを選べ:
このような条件を満たすを答えよ。
アイデア
まず、は多いほうが得だから限界まで増やすことにする。
そして、このとのペアを、残っている中で、aが最大
→bが最小
→aが最大
→…と交互にルールを適用していって並べていく。例を示すと、の時は次のようになる。
このように並べることで、局所的に大小関係が発生するので、奇数番目に現れるものを選んでいけば必ず全体の和の半分より大きい値を得られる。が偶数の時は、最後のindexを1つ前に詰めておけばよい。
乱択でも通ってしまうっぽい…(submission)。
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second typedef pair<int,int> pi; int main() { int n; scanf(" %d", &n); priority_queue<pi> qa,qb; rep(i,n) { int a; scanf(" %d", &a); qa.push(pi(a,i)); } rep(i,n) { int b; scanf(" %d", &b); qb.push(pi(-b,i)); } vector<int> ans; vector<bool> used(n,false); rep(i,n-1) { pi p; if(i%2) { while(1) { p = qb.top(); qb.pop(); if(!used[p.se]) { used[p.se] = true; break; } } } else { while(1) { p = qa.top(); qa.pop(); if(!used[p.se]) { used[p.se] = true; ans.pb(p.se); break; } } } } // last one rep(i,n)if(!used[i]) ans.pb(i); // output sort(all(ans)); printf("%d\n", n/2+1); rep(i,ans.size()) { if(i) printf(" "); printf("%d", ans[i]+1); } printf("\n"); return 0; }