社区讨论

64pts,求大佬帮忙看正确性,悬赏20rmb

P3566[POI 2014] KLO-Bricks参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m4282ya1
此快照首次捕获于
2024/11/29 12:07
去年
此快照最后确认于
2025/11/04 13:41
4 个月前
查看原帖
Rt,找到挂的地方了,但是不会调,所以求各位大佬帮忙看一下
要看的地方在注释下面
CPP
#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
static char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 22, stdin), p1 == p2) ? EOF : *p1++)
#define putchar(X) *O++ = (X)
#define writesp(X) write(X), putchar(' ')
template < typename T >
inline void read(T &X)
{
    X = 0; bool f = false; char ch = getchar();
    while (!isdigit(ch)) {f |= ch == '-'; ch = getchar();}
    while (isdigit(ch)) {X = (X * 10) + (ch ^ 48); ch = getchar();}
    X = f ? -X : X;
}
template < typename T >
inline void write(T X)
{
    if (X == 0) {putchar('0'); return;}
    if (X < 0) {putchar('-'); X = -X;}
    static int cnt = 0, num[21];
    while (X) {*(num + ++cnt) = X % 10; X /= 10;}
    while (cnt) putchar(*(num + cnt--) ^ 48);
}
int n, p, q, cnt;
struct node
{
    int col, num;
    node (const int &_col, const int &_num) : col(_col), num(_num) {}
    bool operator < (const node &b) const {return this->num != b.num ? this->col == q : this->num < b.num;}
};
priority_queue < node > heap;
int ans[maxn];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("P3566.in", "r", stdin);
    freopen("P3566.out", "w", stdout);
#endif
    read(n); read(p); read(q);
    if (n == 1)
    {
        int x;
        read(x);
        if (p != 1 || q != 1 || x > 1) write(0);
        else write(1);
        fwrite(obuf,O - obuf, 1, stdout);
        fclose(stdin);
        fclose(stdout);
        return 0;
    }
    for (int i = 1; i <= n; ++i)
    {
        int x;
        read(x); cnt += x;
        x -= (i == p) + (i == q);
        if (x < 0)
        {
            write(0);
            fwrite(obuf,O - obuf, 1, stdout);
            fclose(stdin);
            fclose(stdout);
            return 0;
        }
        if (x) heap.emplace(i, x);
    }
    ans[1] = p, ans[cnt] = q;
    for (int i = 2; i < cnt; ++i)
    {
        node a = {0, 0};
        if (!heap.empty()) {a = heap.top(); heap.pop();}
        if (ans[i - 1] == a.col)
        {
            node b = {0, 0};
            //错误原因是误判无解,通过输出114514并查看测试点信息发现问题是这里
            //这里的思路是假如第二多的砖没了,说明这里只能重复放同一种颜色,那么无解
            //我觉得没啥问题,但交上去会把有解的情况判成无解
            //所以帮忙看一下是我这里打挂了,还是贪心其他部分写的有问题
            if (heap.empty())
            {
                write(0);
                fwrite(obuf,O - obuf, 1, stdout);
                fclose(stdin);
                fclose(stdout);
                return 0;
            }
            b = heap.top(); heap.pop();
            --b.num, ans[i] = b.col;
            if (b.num) heap.emplace(b);
        }
        else --a.num, ans[i] = a.col;
        if (a.num) heap.emplace(a);
    }
    if (ans[cnt - 1] == ans[cnt]) write(0);
    else
    {
        for (int i = 1; i < cnt; ++i) writesp(ans[i]);
        write(ans[cnt]);
    }
    fwrite(obuf,O - obuf, 1, stdout);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...