与其说这题是贪心题
这题更像一个构造题,非常开阔思维
首先我们随便以一个A或B为关键字排序,然后发现N/2+1这个加1很重要,根据经验暗示我们选第一个
然后接下来我们钦定假设以A为第一关键字排序
于是我们剩下的每两个选一个B那位max的,可以发现B显然是满足条件的,那么A满足条件吗?
a[1].A>=max(a[2].A,a[3].A),min(a[2].A,a[3].A)>=max(a[4].A,a[5].A)以此类推肯定满足条件
于是我们构造出来了方案,偶数最后一个数也选特别判断一下就好了
代码:
#include<bits/stdc++.h> using namespace std; #define debug(x) cerr<<#x<<" = "<<x #define sp <<" " #define el <<endl #define fgx cerr<<" ------------------------------------------------ "<<endl #define LL long long #define DB double #define mpt make_pair #define pb push_back inline LL read(){ LL nm=0; bool fh=true; char cw=getchar(); for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-'); for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0'); return fh?nm:-nm; } #define M 100200 int n; struct Nod{ int x,y,id; inline bool operator <(const Nod b) const{return (x^b.x)?(x>b.x):(y>b.y);} }a[M]; int main(){ n=read(); for(int i=1;i<=n;i++) a[i].x=read(),a[i].id=i; for(int i=1;i<=n;i++) a[i].y=read(); sort(a+1,a+n+1),printf("%d\n%d ",(n>>1)+1,a[1].id); int pos=2; while(pos+1<=n){ if(a[pos].y>=a[pos+1].y) printf("%d ",a[pos].id); else printf("%d ",a[pos+1].id); pos+=2; } if(pos<=n) printf("%d",a[pos].id); puts("");return 0; }