题意:给你两个数列a,b,你要输出k个下标，使得这些下标对应的a的和大于整个a数列的和的1/2.同时这些下标对应的b
//题解：首先将条件换一种说法，就是要取floor(n/2)+1个数使得这些数大于剩下的数。然后想到两种取法，一种是排好序选前半段。令一种取法是两个两个分组，每组取大的那个。
//然后就可以（很困难地）想到一种巧妙的取法，先用一个结构体保存a,b,idx,按照a从大到小排序，先取第一个，再对剩下的每两个一组取其中b更大的。这样保证了被选出
//的b一定大于剩下的b，也就满足了条件。然后考虑a，按照前面的分组，每组的a并不一定选到了大的。但是我们（并没有）观察到第一个选的a （也就是a的最大值）一定大于第一组没选到的那个a、第一组选的a一定大于第二组没选出的a···；
//同理这样选出的a也一定大于剩下的a。所以算法就是读取，排序，一个循环 。（codeforces上python只有三行。。。）
ac代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<stdio.h> #include<algorithm> using namespace std; const int maxn = 1e5 + 5; struct node { int a, b, idx; }s[maxn]; bool cmp(node x,node y) { return x.a > y.a; } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { scanf("%d", &s[i].a); s[i].idx = i; } for (int i = 1; i <= n; i++) { scanf("%d", &s[i].b); } sort(s + 1, s + 1 + n,cmp); cout << n / 2 +1<<endl; cout << s[1].idx; for (int i = 2; i <= n; i += 2) { int ans; s[i].b > s[i + 1].b ? ans = s[i].idx : ans=s[i + 1].idx; printf(" %d", ans); } //cin >> n; }
附 ：codeforces上看到的神级头文件，
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <set> #include <map> #include <queue> #include <cstdlib> #include <string> #include <complex> #include <bitset> #include <cmath> using namespace std; #define mst(x,v) memset(x,v,sizeof(x)) #define rp(k,x,v) for(int k = x;k<v;++k) #define rps(s) for(int i = 0;s[i];++i) #define RP(k,x,v) for(int k = x;k<=v;++k) #define lp(k,x,v) for(int k = x;k>v;--k) #define LP(k,x,v) for(int k = x;k>=v;--k) #define ll long long #define ull unsigned long long #define fr(file) freopen(file,"r",stdin); #define fw(file) freopen(file,"w",stdout); #define lowbit(x) (x&-x) #define adde(u,v) edg[++ecnt]=Edge(u,v,g[u]),g[u]=ecnt #define addew(u,v,w) edg[++ecnt]=Edge(u,v,g[u],w),g[u]=ecnt #define addedg(u,v,w,cap) edg[++ecnt]=Edge(u,v,g[u],w,cap),g[u]=ecnt,edg[++ecnt]=Edge(v,u,g[v],-w,0),g[v]=ecnt #define fson for(int i = g[u];~i;i=edg[i].next) #define LB lower_bound #define UB upper_bound #define inp(n,a) RP(i,1,n) ru(a[i]); #define pii pair<int,int> #define pll pair<ll,ll> #define pil pair<int,ll> #define pdd pair<double,double> #define piii pair<pii,int> #define plll pair<pll,ll> #define mpt int mid = l+r>>1; #define ls (k<<1) #define rs (k<<1|1) #define INF (1<<28) #define LINF (1LL << 60) #define initi(n,a) RP(i,1,n) a[i]=INF; #define initl(n,a) RP(i,1,n) a[i]=LINF; #define dsui(n,p) RP(i,1,n) p[i]=i; #define all(a) a.begin(),a.end() #define inr (ql<=l && r<=qr) #define cpx complex<double> #define spf(s,a) RP(i,1,n) s[i]=s[i-1]+a[i] #define ssf(s,a) lp(i,n,0) g[i]=g[i+1]+a[i] #define upmax(a,b) a=max(a,b) #define upmin(a,b) a=min(a,b) #define getmax(maxd,a,n) RP(i,1,n) upmax(maxd,a[i]) #define getmin(mind,a,n) RP(i,1,n) upmin(mind,a[i]) char READ_DATA; int SIGNAL_INPUT; template <typename Type> inline Type ru(Type &v) { SIGNAL_INPUT = 1; while ((READ_DATA = getchar()) < '0' || READ_DATA > '9') if (READ_DATA == '-') SIGNAL_INPUT = -1; else if (READ_DATA == EOF) return EOF; v = READ_DATA - '0'; while ((READ_DATA = getchar()) >= '0' && READ_DATA <= '9') v = v * 10 + READ_DATA - '0'; v *= SIGNAL_INPUT; return v; } template<typename A, typename B > inline char ru(A&x, B&y) { if (ru(x) == EOF) return EOF; ru(y); return 2; } template<typename A, typename B, typename C>inline char ru(A&x, B&y, C&z) { if (ru(x) == EOF) return EOF; ru(y); ru(z); return 3; } template<typename A, typename B, typename C, typename D>inline char ru(A&x, B&y, C&z, D&w) { if (ru(x) == EOF) return EOF; ru(y); ru(z); ru(w); return 4; } int TEMP; inline void swap(int &a, int &b) { TEMP = a; a = b; b = TEMP; } struct Vector { double x, y; Vector(double _x = 0.0, double _y = 0.0) { x = _x; y = _y; } int operator<(const Vector &cmp) const { return x < cmp.x || (x == cmp.x && y < cmp.y); } }; typedef Vector Point; inline double dis(Point &a, Point &b) { return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2)); } struct Edge { int u, v, next; int w; int cap, flow; Edge(int _u = 0, int _v = 0, int nxt = -1, int _w = 1, int _cap = 0) { u = _u; v = _v; w = _w; cap = _cap; flow = 0; next = nxt; } int operator<(const Edge &b) const { return w < b.w; } }; namespace BalancedTreeNode { struct Node { Node *ch[2], *fa; int v, s, rev, setv, sum, lsum, rsum, mxsum; Node(int val = 0) { v = sum = val; s = rev = 0; lsum = rsum = val; mxsum = val; setv = INF; } int cmpv(int val) { return val == v ? -1 : val>v; } int cmprk(int rk) { return rk == ch[0]->s + 1 ? -1 : rk > ch[0]->s + 1; } void pushdown() { if (rev) { swap(ch[0], ch[1]); swap(lsum, rsum); if (ch[0]->v != -INF) ch[0]->rev ^= 1; if (ch[1]->v != -INF) ch[1]->rev ^= 1; rev = 0; } if (setv != INF) { v = setv; lsum = rsum = mxsum = max(v, sum = v*s); if (ch[0]->v != -INF) ch[0]->setv = setv; if (ch[1]->v != -INF) ch[1]->setv = setv; setv = INF; } } void maintain() { pushdown(); ch[0]->pushdown(); ch[1]->pushdown(); s = ch[0]->s + ch[1]->s + 1; sum = ch[0]->sum + ch[1]->sum + v; lsum = rsum = -INF; mxsum = -INF; upmax(lsum, max(ch[0]->lsum, ch[0]->sum + v + max(0, ch[1]->lsum))); upmax(rsum, max(ch[1]->rsum, ch[1]->sum + v + max(0, ch[0]->rsum))); upmax(mxsum, max(0, ch[0]->rsum) + v + max(0, ch[1]->lsum)); upmax(mxsum, max(ch[0]->mxsum, ch[1]->mxsum)); } }; Node* null = new Node(-INF); Node* newnode(int val) { Node* k = new Node(val); k->ch[0] = k->ch[1] = k->fa = null; k->maintain(); return k; } inline void rotate(Node *x, const int d) { Node* y = x->fa; y->ch[d ^ 1] = x->ch[d]; if (x->ch[d] != null) x->ch[d]->fa = y; x->fa = y->fa; if (y->fa->ch[0] == y) x->fa->ch[0] = x; else if (y->fa->ch[1] == y) x->fa->ch[1] = x; y->fa = x; x->ch[d] = y; y->maintain(); x->maintain(); } Node* insert(Node* &k, int val) { if (k == null) return k = newnode(val); else { int d = k->cmpv(val); if (d == -1) return k; int reach = k->ch[d] == null; Node* p = insert(k->ch[d], val); k->maintain(); if (reach) k->ch[d]->fa = k; return p; } } void Remove_Tree(Node* k) { if (k->ch[0] != null) Remove_Tree(k->ch[0]); if (k->ch[1] != null) Remove_Tree(k->ch[1]); delete k; } int Rank(Node *k, int val) { int rk = 0, d; while (k != null) { k->pushdown(); d = k->cmpv(val); if (d) rk += k->ch[0]->s + 1; if (d == -1) break; k = k->ch[d]; } return rk; } Node* Kth(Node* k, int rk) { int d; while (k != null) { k->pushdown(); d = k->cmprk(rk); if (d == -1) return k; if (d) rk -= k->ch[0]->s + 1; k = k->ch[d]; } return null; } } namespace Splay { using namespace BalancedTreeNode; inline int isfa(Node *x, Node* &y) { return (y = x->fa) != null && (y->ch[0] == x || y->ch[1] == x); } inline void splay(Node* x) { x->pushdown(); Node *y, *z; while (isfa(x, y)) { if (isfa(y, z)) { z->pushdown(); y->pushdown(); x->pushdown(); int d = y == z->ch[0]; if (x == y->ch[d]) rotate(x, d ^ 1), rotate(x, d); else rotate(y, d), rotate(x, d); } else { y->pushdown(); x->pushdown(); rotate(x, x == y->ch[0]); break; } } } inline void Insert(Node* &k, int val) { splay(k = insert(k, val)); } Node* build(int *a, int l, int r) { if (l > r) return null; mpt; Node* k = newnode(a[mid]); k->ch[0] = build(a, l, mid - 1); k->ch[1] = build(a, mid + 1, r); if (k->ch[0] != null) k->ch[0]->fa = k; if (k->ch[1] != null) k->ch[1]->fa = k; if (mid == 0) k->sum = 0; k->maintain(); return k; } Node* merge(Node *left, Node *right) { splay(left = Kth(left, left->s)); left->ch[1] = right; right->fa = left; left->maintain(); return left; } void split(Node *k, int rk, Node* &left, Node* &right) { splay(k = Kth(k, rk)); left = k; right = left->ch[1]; left->ch[1] = null; right->fa = null; left->maintain(); } }; namespace LCT { using namespace Splay; Node* access(Node* k) { Node* p = null; while (k != null) { splay(k); k->ch[1] = p; p = k; k->maintain(); k = k->fa; } return p; } void makeroot(Node* k) { access(k)->rev ^= 1; splay(k); } Node* getroot(Node* k) { k = access(k); k->pushdown(); while (k->ch[0] != null) { k = k->ch[0]; k->pushdown(); } return k; } void link(Node* x, Node* y) { makeroot(x); x->fa = y; access(x); } void cut(Node* x, Node* y) { makeroot(x); access(y); splay(y); y->ch[0]->fa = null; y->ch[0] = null; y->maintain(); } } ll gcd(ll a, ll b) { while (b) { a %= b; swap(a, b); } return a; } void exgcd(ll a, ll b, ll &d, ll &x, ll &y) { if (!b) d = a, x = 1, y = 0; else exgcd(b, a%b, d, y, x), y -= x*(a / b); } ll inv(ll a, ll mod) { ll d, x, y; exgcd(a, mod, d, x, y); return d == 1 ? (x + mod) % mod : -1; } int bitcnt(ll x) { int cnt = 0; while (x) { cnt += (x & 1); x >>= 1; } return cnt; } ll key = 257; ll mod = 1e9 + 7; ll qkmul(ll a, ll b) { ll ans = 0, x = a; while (b) { if (b & 1) (ans += x) %= mod; (x += x) %= mod; b >>= 1; } return ans; } ll qkpow(ll a, ll b) { ll ans = 1, x = a; while (b) { if (b & 1) (ans *= x) %= mod; (x *= x) %= mod; b >>= 1; } return ans; } const int maxn = 1e5 + 7, maxp = 1e6; const double pi = acos(-1.0), alpha = 0.65, eps = 1e-9; inline int dcmp(double a, double b) { return abs(a - b) < eps; } struct DSU { int p[maxn]; void init(int n) { RP(i, 0, n) p[i] = i; } int find(int u) { return u == p[u] ? u : p[u] = find(p[u]); } void merge(int u, int v) { u = find(u); v = find(v); p[u] = (u^v) ? v : p[u]; } }; struct BIT { ll *t, n; void init(int sz) { t = new ll[sz + 1]; memset(t, 0, sizeof(ll)*(sz + 1)); n = sz; } void add(int x, ll d) { while (x <= n) { t[x] += d; x += lowbit(x); } } ll qry(int x) { ll ans = 0; while (x) { ans += t[x]; x -= lowbit(x); } return ans; } int qry(int l, int r) { return qry(r) - qry(l - 1); } }; int N; struct SegTree { struct Node { int lc, rc; ll sum, add; }t[maxn * 2]; void maintain(int k,int l,int r) { int lc = t[k].lc, rc = t[k].rc; (t[k].sum = t[lc].sum + t[rc].sum + t[k].add*(r - l + 1) % mod) %= mod; } void pushdown(int k,int l,int r) { if (t[k].add) { if (l == r) { t[k].sum += t[k].add; t[k].add = 0; return; } mpt; int lc = t[k].lc, rc = t[k].rc; (t[lc].add += t[k].add)%=mod; maintain(lc, l, mid); (t[rc].add += t[k].add)%=mod; maintain(rc, mid + 1, r); t[k].add = 0; } } int ql, qr, tot; ll qv; void init(int _N) { N = _N; tot = 1; } void build(int k = 1, int l = 1, int r = N) { if (l == r) return; else { mpt; build(t[k].lc = ++tot, l, mid); build(t[k].rc = ++tot, mid + 1, r); } } void add(int k = 1, int l = 1, int r = N) { if (inr) { (t[k].add += qv) %= mod; } else { mpt; if (ql <= mid) add(t[k].lc, l, mid); if (qr > mid) add(t[k].rc, mid + 1, r); } maintain(k, l, r); } ll qry(int k = 1, int l = 1, int r = N,ll add=0) { if (inr) { return (t[k].sum + add*(r - l + 1) % mod) % mod; } else { mpt; ll ans = 0; add += t[k].add; if (ql <= mid) (ans += qry(t[k].lc, l, mid, add)) %= mod; if (qr > mid) (ans += qry(t[k].rc, mid + 1, r, add)) %= mod; return ans; } } void Add(int l, int r, ll v) { ql = l; qr = r; qv = v; add(); } ll Qry(int l, int r) { ql = l; qr = r; return qry(); } }; struct MCMF { int n, m, s, t; Edge edg[maxn]; int ecnt, g[maxn], d[maxn], a[maxn], inq[maxn], pre[maxn]; void init(int N) { n = N; mst(g, ecnt = -1); } void addedge(int u, int v, int w, int cap) { addedg(u, v, w, cap); } queue<int> q; int bfs() { RP(i, 1, n) d[i] = INF; q.push(s); int u, v; d[s] = 0; inq[s] = 1; a[s] = INF; while (!q.empty()) { u = q.front(); q.pop(); fson { v = edg[i].v; if (edg[i].cap>edg[i].flow && d[v] > d[u] + edg[i].w) { d[v] = d[u] + edg[i].w; a[v] = min(a[u], edg[i].cap - edg[i].flow); pre[v] = i; if (!inq[v]) { q.push(v); inq[v] = 1; } } } inq[u] = 0; } return d[t] != INF; } void augment(int &cost) { cost += a[t] * d[t]; int u = t; while (u != s) { edg[pre[u]].flow += a[t]; edg[pre[u] ^ 1].flow -= a[t]; u = edg[pre[u]].u; } } int mcmf(int S, int T) { s = S; t = T; int cost = 0; while (bfs()) { augment(cost); } return cost; } }; struct Dinic { int n, m, s, t; Edge edg[maxn]; int ecnt, g[maxn], d[maxn], vis[maxn], cur[maxn]; void init(int N) { n = N; mst(g, ecnt = -1); } void addedge(int u, int v, int cap) { addedg(u, v, 0, cap); } queue<int> q; int bfs() { mst(vis, 0); q.push(s); int u, v; vis[s] = 1; while (!q.empty()) { u = q.front(); q.pop(); fson { v = edg[i].v; if (edg[i].cap>edg[i].flow && !vis[v]) { d[v] = d[u] + 1; vis[v] = 1; q.push(v); } } } return vis[t]; } int dfs(int u, int a) { if (u == t || !a) return a; int flow = 0, aug, v; for (int &i = cur[u]; ~i; i = edg[i].next) { v = edg[i].v; if (d[v] == d[u] + 1 && (aug = dfs(v, min(a, edg[i].cap - edg[i].flow)))) { flow += aug; a -= aug; edg[i].flow += aug; edg[i ^ 1].flow -= aug; if (!a) break; } } return flow; } int maxflow(int S, int T) { s = S, t = T; int flow = 0; while (bfs()) { RP(i, 1, n) cur[i] = g[i]; flow += dfs(s, INF); } return flow; } }; struct Mat { int n, m; ll a[5][5]; Mat(int r = 0, int c = 0) { n = r; m = c; mst(a, 0); } static Mat idmat(int n) { Mat ans(n, n); rp(i, 0, n) ans[i][i] = 1; return ans; } ll* operator[](int i) { return a[i]; } Mat operator*(Mat b) { Mat ans(n, b.m); rp(i, 0, n) rp(j, 0, b.m) rp(k, 0, m) (ans[i][j] += a[i][k] * b[k][j] % mod) %= mod; return ans; } }; Mat qkpow(Mat &A, ll b) { Mat ans = Mat::idmat(A.n), x = A; while (b) { if (b & 1) ans = ans * x; x = x*x; b >>= 1; } return ans; } int n, a[maxn], b[maxn], c[maxn]; int cmp(const int &i, const int &j) { return a[i] > a[j]; } int main() { ru(n); inp(n, a); inp(n, b); RP(i, 1, n) c[i] = i; sort(c + 1, c + n + 1, cmp); printf("%d %d", n / 2 + 1, c[1]); for (int i = 2; i <= n; i += 2) { if (b[c[i]] > b[c[i + 1]]) printf(" %d", c[i]); else printf(" %d", c[i + 1]); } }
的和也大于整个b数列的和的1/2.k<= .(这个条件很关键)
//题解：首先将条件换一种说法，就是要取floor(n/2)+1个数使得这些数大于剩下的数。然后想到两种取法，一种是排好序选前半段。令一种取法是两个两个分组，每组取大的那个。
//然后就可以（很困难地）想到一种巧妙的取法，先用一个结构体保存a,b,idx,按照a从大到小排序，先取第一个，再对剩下的每两个一组取其中b更大的。这样保证了被选出
//的b一定大于剩下的b，也就满足了条件。然后考虑a，按照前面的分组，每组的a并不一定选到了大的。但是我们（并没有）观察到第一个选的a （也就是a的最大值）一定大于第一组没选到的那个a、第一组选的a一定大于第二组没选出的a···；
//同理这样选出的a也一定大于剩下的a。所以算法就是读取，排序，一个循环 。（codeforces上python只有三行。。。）
ac