社区讨论
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 条回复,欢迎继续交流。
正在加载回复...