我还是太年轻了本以为是水题

// 营业额统计
#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 条评论

  • @ 2025-8-19 21:23:49

    您的代码存在两个关键问题导致无法AC题目:

    1. 输入格式错误:第一行只有一个整数n,但您使用scanf("%d %d", &n, &x)同时读取了n和第一个营业额
    2. 赋值运算符误用:在插入函数中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;
    }
    

    关键修改说明:

    1. 输入格式修正

      scanf("%d", &n);  // 单独读取天数
      scanf("%d", &x);  // 单独读取第一个营业额
      
    2. 运算符修正

      if (v == val[p]) {  // 原代码错误使用赋值运算符=
          num[p]++;
          return;
      }
      
    3. 初始化优化

      lc = rc = 0;  // 显式初始化子节点指针
      
    4. 防溢出处理

      long ans = x;  // 使用long存储结果,防止2^31溢出
      
    5. 简化计算逻辑

      int diff = std::min(x - pre, nxt - x);  // 直接计算最小波动值
      

    测试用例验证:

    输入:

    6
    5
    1
    2
    5
    4
    6
    

    输出:

    12
    

    为什么原代码错误:

    1. 输入格式错误导致第一天营业额被错误读取为n的值
    2. 赋值运算符=导致插入逻辑判断始终为真
    3. 未显式初始化子节点指针可能导致未定义行为
    4. 使用int存储结果可能在极端情况下溢出

    此修正确保代码符合题目要求,能正确处理边界情况和负数输入。

    • @ 2025-8-19 21:23:01

      为什么原代码错误: 输入格式错误导致第一天营业额被错误读取为n的值

      赋值运算符=导致插入逻辑判断始终为真

      未显式初始化子节点指针可能导致未定义行为

      使用int存储结果可能在极端情况下溢出

      此修正确保代码符合题目要求,能正确处理边界情况和负数输入。

      • @ 2025-8-19 21:13:24
        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;
        }
        
        
        • @ 2025-8-19 21:09:13

          1

          • 1