CF720A Closing ceremony

Codeforces

Luogu

分析

好像以前看到过...于是切了

考虑先给从 $(0,0)$ 进来的人安排座位。贪心地想,我们会把每个人安排到能坐的离 $(0,m+1)$ 最远的位置。那么用堆维护一下能坐的位置就好了。

然后会剩下一些没有人坐的座位,这些座位应该分给从 $(0,m+1)$ 进来的人,而且耐力大的人的座位离 $(0,m+1)$ 会远。

不可行的话就很容易判断了,如果一个人没有座位或者座位太远就不可行。

具体实现及细节见代码中的注释。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10;

int n,m,k,tot=0,b[N];
struct node { int dis1,dis2; } a[N];
inline int cmp1(node a,node b) { return a.dis1<b.dis1; }
bool operator <(node a,node b) { return a.dis2<b.dis2; }
priority_queue<node> Q;
inline int cmp2(int a,int b) { return a<b; }
inline int cmp3(int a,int b) { return a>b; }

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j)
            a[++tot]=(node){i+j,i+m+1-j}; //预处理所有座位的距离
    sort(a+1,a+tot+1,cmp1); int pos=1;
    k=read();
    for (re int i=1;i<=k;++i) b[i]=read();
    sort(b+1,b+k+1,cmp2);
    for (re int i=1;i<=k;++i) {
        while (a[pos].dis1<=b[i]&&pos<=tot) Q.push(a[pos]),++pos;
        if (Q.empty()) { puts("NO"); return 0; } // 没有座位了
        Q.pop(); // 把 dis2 最大的当成自己的座位
    }
    for (re int i=pos;i<=n*m;++i) Q.push(a[i]); // 把剩下的座位丢进堆里
    k=read();
    for (re int i=1;i<=k;++i) b[i]=read();
    sort(b+1,b+k+1,cmp3); // 耐力大的座位远
    for (re int i=1;i<=k;++i) {
        if (Q.top().dis2>b[i]) { puts("NO"); return 0; } // 太远了
        Q.pop();
    }
    puts("YES"); return 0;
}
最后修改:2019 年 10 月 04 日 03 : 10 PM

发表评论