【luogu CF720A】Closing ceremony

这个题目显然网络流过不了,所以需要考虑贪心,考虑对于从(0,0)出发的点,每一个都尽可能的去选择自己能到达,并且距离(0, m+1)尽可能远的格子。然后就完了……

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 1e4 + 10;

int n, m, k, l, lx, a[ms], tot;

struct node
{
    int x, y, z, dis;
    inline bool operator < (const node &a) const
    {
        return z < a.z;
    }
}tmp[ms];

priority_queue <node> qwq;

inline bool cmp(node a, node b)
{
    return a.dis < b.dis;
}

int main()
{
    re(n), re(m), re(k);
    for(ri i = 1; i <= k; i ++)
        re(a[i]);
    sort(a + 1, a + 1 + k);
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
            tmp[++ tot] = (node){i, j, m + 1 - j + i, i + j};
    sort(tmp + 1, tmp + 1 + tot, cmp);
    int ta = 1; bool fl = 0;
    for(ri i = 1; i <= k; i ++)
    {
        while(a[i] >= tmp[ta].dis && ta <= tot)
            qwq.push(tmp[ta]), ta ++;
        if(qwq.empty())
        {
            fl = 1; break;
        }
        //cout << qwq.top().z << '\n'; 
        qwq.pop();
    }
    while(ta <= tot)
        qwq.push(tmp[ta]), ta ++;
    re(k);
    for(ri i = 1; i <= k; i ++)
        re(a[i]);
    sort(a + 1, a + 1 + k);
    for(ri i = k; i > 0; i --)
    {
        if(a[i] < qwq.top().z)
        {
            fl = 1; break;
        }
        //cout << qwq.top().z << '\n'; 
        qwq.pop();
    }
    printf("%s", fl ? "NO" : "YES");
    system("pause");
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注