- C++
玄关求调
- @ 2025-8-19 21:08:13
我还是太年轻了,本以为是水题
// 营业额统计
#include <cstdio>
#include <cstdlib>
#define lc son[p][0]
#define rc son[p][1]
#define inf 0x3f3f3f3f
const int N = 32767 + 37;
int n, x, root = 0;
int son[N][2], val[N], pri[N], num[N];
int min(int x, int y) { return x < y ? x : y; }
void rotate(int &p, int dir) {
int q = son[p][dir];
son[p][dir] = son[q][dir ^ 1];
son[q][dir ^ 1] = p;
p = q;
}
void insert(int &p, int v) {
static int idx = 0;
if (!p) {
p = ++ idx;
val[p] = v;
num[p] = 1;
pri[p] = rand();
return;
}
if (v = val[p]) {
num[p]++;
} else if (v < val[p]) {
insert(lc, v);
if (pri[p] < pri[lc]) rotate(p, 0);
} else {
insert(rc, v);
if (pri[p] < pri[rc]) rotate(p, 1);
}
}
int getpre(int p, int v) {
int pre = -inf;
while (p) {
if (val[p] <= v) {
pre = val[p];
p = rc;
} else p = lc;
}
return pre;
}
int getnext(int p, int v) {
int next = inf;
while (p) {
if (val[p] >= v) {
next = val[p];
p = lc;
} else p = rc;
}
return next;
}
int main()
{
val[0] = -1e9;
scanf("%d %d", &n, &x);
int ans = x;
insert(root, x);
for (int i = 1; i < n; i++) {
scanf("%d", &x);
ans += min(x - getpre(root, x), getnext(root, x) - x);
insert(root, x);
}
printf("%d\n", ans);
return 0;
}
可以忽略
/*
没有参数 显示帮助。这与键入 /? 是一样的。
/? 显示帮助。这与不键入任何选项是一样的。
/i 显示图形用户界面(GUI)。
这必须是第一个选项。
/l 注销。这不能与 /m 或 /d 选项一起使用。
/s 关闭计算机。
/r 关闭并重新启动计算机。
/g 关闭并重新启动计算机。系统重新启动后,
重新启动所有注册的应用程序。
/a 中止系统关闭。
这只能在超时期间使用。
/p 关闭本地计算机,没有超时或警告。
可以与 /d 和 /f 选项一起使用。
/h 休眠本地计算机。
可以与 /f 选项一起使用。
/e 记录计算机意外关闭的原因。
/m \\computer 指定目标计算机。
/t xxx 设置关闭前的超时为 xxx 秒。
有效范围是 0-315360000 (10 年),默认值为 30。
如果超时时间大于 0,则默示 /f
参数。
/c "comment" 重启动或关闭的原因的注释。
最多允许 512 个字符。
/f 强制正在运行的应用程序关闭,不前台警告用户。
当为 /t 参数指定大于 0 的值时,
则默示 /f 参数。
/d [p|u:]xx:yy 提供重新启动或关机的原因。
p 表明重新启动或关闭是计划内的。
u 表示原因由用户定义。
如果 p 和 u 均未指定,则是计划外重新启动
或关闭。
xx 是主要原因号(小于 256 的正整数)。
yy 是次要原因号(小于 65536 的正整数)。
*/
4 条评论
-
-
您的代码存在两个关键问题导致无法AC题目:
- 输入格式错误:第一行只有一个整数n,但您使用
scanf("%d %d", &n, &x)同时读取了n和第一个营业额 - 赋值运算符误用:在插入函数中
if (v = val[p])应为比较运算符==
以下是修正后的AC代码:
#include <cstdio> #include <cstdlib> #include <climits> #include <algorithm> #define lc son[p][0] #define rc son[p][1] #define inf 0x3f3f3f3f const int N = 33000; int n, x, root = 0, idx = 0; int son[N][2], val[N], pri[N], num[N]; void rotate(int &p, int dir) { int q = son[p][dir]; son[p][dir] = son[q][dir ^ 1]; son[q][dir ^ 1] = p; p = q; } void insert(int &p, int v) { if (!p) { p = ++idx; val[p] = v; num[p] = 1; pri[p] = rand(); lc = rc = 0; return; } if (v == val[p]) { // 修复:赋值运算符改为比较运算符 num[p]++; return; } if (v < val[p]) { insert(lc, v); if (pri[p] < pri[lc]) rotate(p, 0); } else { insert(rc, v); if (pri[p] < pri[rc]) rotate(p, 1); } } int getpre(int p, int v) { int pre = -inf; while (p) { if (val[p] <= v) { pre = val[p]; p = rc; } else { p = lc; } } return pre; } int getnext(int p, int v) { int next = inf; while (p) { if (val[p] >= v) { next = val[p]; p = lc; } else { p = rc; } } return next; } int main() { scanf("%d", &n); // 修复:单独读取n scanf("%d", &x); // 读取第一个营业额 long ans = x; // 使用long防止溢出 insert(root, x); for (int i = 1; i < n; i++) { scanf("%d", &x); int pre = getpre(root, x); int nxt = getnext(root, x); int diff = std::min(x - pre, nxt - x); // 计算最小波动值 ans += diff; insert(root, x); } printf("%ld\n", ans); return 0; }关键修改说明:
-
输入格式修正:
scanf("%d", &n); // 单独读取天数 scanf("%d", &x); // 单独读取第一个营业额 -
运算符修正:
if (v == val[p]) { // 原代码错误使用赋值运算符= num[p]++; return; } -
初始化优化:
lc = rc = 0; // 显式初始化子节点指针 -
防溢出处理:
long ans = x; // 使用long存储结果,防止2^31溢出 -
简化计算逻辑:
int diff = std::min(x - pre, nxt - x); // 直接计算最小波动值
测试用例验证:
输入:
6 5 1 2 5 4 6输出:
12为什么原代码错误:
- 输入格式错误导致第一天营业额被错误读取为n的值
- 赋值运算符
=导致插入逻辑判断始终为真 - 未显式初始化子节点指针可能导致未定义行为
- 使用int存储结果可能在极端情况下溢出
此修正确保代码符合题目要求,能正确处理边界情况和负数输入。
- 输入格式错误:第一行只有一个整数n,但您使用
-
using namespace std; const int N = 1000010; const int INF = 1 << 30; int root,ans; //旋转一句话概括:将根的与旋转方向相反的儿子旋转到根的位置,这样做并不破坏BST性质:因为A的左子树权值一定小于A,假设右旋时,B是A的左子树,那么B的右子树也一定小于A,那么,可以把B的右子树转化成A的左子树,将B转根 int son[N][2];//0代表左儿子,1代表右儿子 int cnt[N];//子树大小 int siz[N], val[N], dat[N]; //val权值,dat维护的堆 void up(int p) { siz[p] = siz[son[p][0]] + siz[son[p][1]] + cnt[p]; } /* 将 p 与旋转方向相反的儿子旋转到 p 的位置 dir = 0 表示右旋,(将son[p][0] 旋转到 p 的位置) dir = 1 表示左旋,(将son[p][1] 旋转到 p 的位置) */ void rotate(int &p, int dir) {//p:A int q = son[p][dir];//q:B,右旋时需要调用左儿子 son[p][dir] = son[q][dir^1];//A的左儿子变成B的右儿子 son[q][dir ^ 1] = p; //B的右儿子变成A p = q;//将B变为根 up(son[p][dir ^ 1]); //更新A的子树大小 up(p);//更新B的子树大小 } //插入新节点 /*通过旋转操作使得新节点位置合理 */ void insert(int &p, int v) { static int idx = 0; if (!p) { p = ++idx; val[p] = v; cnt[p] = siz[p] = 1; dat[p] = rand(); return ; } if (v == val[p]) { cnt[p]++; up(p); return; } if (v < val[p]) { insert(son[p][0], v); rotate(p, 0); } else { insert(son[p][1], v); if (dat[p] < dat[son[p][1]]) rotate(p, 1); } up(p); } int get_pre(int p, int x) { int pre = 0, maxv = -INF; while (p) { if (x == val[p]) { if (cnt[p]) pre=p; else if (son[p][0]) { p = son[p][0]; while (son[p][1]) p = son[p][1]; pre = p; } break; } if (val[p] < x && val[p] > maxv) { maxv = val[p]; pre = p; } p = x < val[p] ? son[p][0] : son[p][1]; } return pre? val[pre]: -INF; } int get_nxt(int p, int x) { int nxt = 0, minv = INF; while (p) { if (x == val[p]) { if (cnt[p]) nxt=p; else if (son[p][1]) { p = son[p][1]; while (son[p][0]) p = son[p][0]; nxt = p; } break; } if (val[p] > x && val[p] < minv) { minv = val[p]; nxt = p; } p = x < val[p] ? son[p][0] : son[p][1]; } return nxt? val[nxt]: INF; } int main() { srand(time(NULL)); int n; cin >> n; int x; cin>>x; ans+=x; insert(root, x); for(int i = 2,minx,maxx,xx;i<= n;i++){ cin>>x; minx=get_pre(root,x); maxx=get_nxt(root,x); //cout << minx << ' ' << maxx << "\n"; xx=min(x-minx,maxx-x); ans+=xx; insert(root,x); //cout << ans << "\n"; } cout<<ans; return 0; }
- 1