每日一题 CF798D Mike and distribution 题解

与其说这题是贪心题
这题更像一个构造题，非常开阔思维
首先我们随便以一个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;
}