[Codeforces] 798D. Mike and distribution

題目連結:http://codeforces.com/problemset/problem/798/D

---

很久以前比賽的時候沒寫出來，最近又再想還是想不到，只好去看題解QQ
大致的想法是，會發現對於$a$我們其實只要在$a$的任意排列的裡面選$a_{2i}$跟$a_{2i+1}$中比較大的人的index，那加起來就一定會夠。但是如果只是無腦的這樣挑很有可能$b$不會符合，所以不妨想想我們把$a$排序一下，並且一定選第一個，接著看相對映的$b$哪個index比較大，就挑他，這樣的話因為$b$一定是好的(跟前面講的一樣)，而$a$若是每次都挑到比較小的那個也不會爛，因為我們已經挑了最大的那個(可以想像成$a$是從$0$開始挑比較大的，$b$是從$1$開始挑比較大的之類的)。

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;

int a[N], b[N], p[N], ans[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<n;i++) cin>>b[i];
	for(int i=0;i<n;i++) p[i]=i;
	sort(p, p+n, [](int x, int y){
		return a[x] > a[y];
	});
	cout<<n/2+1<<'\n';
	ans[0] = p[0];
	for(int i=1;i<n;i+=2){
		if(b[p[i]] > b[p[i+1]]) ans[(i+1)/2] = p[i];
		else ans[(i+1)/2] = p[i+1];
	}
	if(n%2==0) ans[n/2] = p[n-1];
	for(int i=0;i<n/2+1;i++) cout<<ans[i]+1<<" \n"[i==n/2];
	return 0;
}