[NOIP 2018 普及组] 龙虎斗

GitHub 跳转原题关系图返回列表

先算出加入 s1 后的双方气势差，再枚举第二次投放位置，比较加入 s2 后的差值绝对值。

OJ: luogu

题目 ID: P5016

难度:普及-

标签:模拟枚举

日期: 2026-06-19 01:07

题意

棋盘上有 n 个兵营，以第 m 个兵营为分界：

左边属于龙
右边属于虎
第 m 个兵营不属于任何一方

一个兵营对某一方贡献的气势等于：

工兵数 × 到 m 的距离

先有一次固定事件：往 p1 号兵营加入 s1 位工兵。
然后你可以再选择一个兵营 p2，把 s2 位工兵全部放进去。

要求让最后龙方和虎方气势差的绝对值尽可能小，输出这个 p2。

思路

先看最直观的做法：

枚举每一个 p2，然后重新统计一遍加入 s1 和 s2 之后双方的总气势，比较差值绝对值。

这个办法很直接，也方便拿来对拍：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;

int n, m, p1;
long long s1, s2;
long long c[MAXN];

long long calc_diff_after_choose(int p2) {
    long long dragon = 0;
    long long tiger = 0;

    for (int i = 1; i <= n; i++) {
        long long cnt = c[i];

        if (i == p1) {
            cnt += s1;
        }
        if (i == p2) {
            cnt += s2;
        }

        if (i < m) {
            dragon += cnt * (m - i);
        }
        else if (i > m) {
            tiger += cnt * (i - m);
        }
    }

    return dragon - tiger;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    cin >> m >> p1 >> s1 >> s2;

    int ans = 1;
    long long best_abs = -1;

    // 直接枚举最后把 s2 放到哪个兵营，并重新统计双方气势。
    for (int p2 = 1; p2 <= n; p2++) {
        long long diff = calc_diff_after_choose(p2);
        long long cur_abs = llabs(diff);
        if (best_abs == -1 || cur_abs < best_abs ||
            (cur_abs == best_abs && p2 < ans)) {
            best_abs = cur_abs;
            ans = p2;
        }
    }

    cout << ans << '\n';

    return 0;
}

但正式做法没必要每次都从头重算。

先把第一次加入 s1 之后的双方气势差记成：

diff = dragon - tiger

接下来枚举 p2 时：

如果 p2 < m，说明 s2 加到龙方，diff 会增加 s2 × (m - p2)
如果 p2 > m，说明 s2 加到虎方，diff 会减少 s2 × (p2 - m)
如果 p2 = m，双方气势都不变

所以每个位置的结果都能在 $O(1)$ 算出来。

这样只要：

先算出第一次事件后的 diff
枚举所有 p2
计算新的差值绝对值
取最小值；若相同取更小的兵营编号

就可以了。

注意：官方题面要求如果有多个最优答案，输出编号最小的兵营。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, m, p1, p2_ans;
long long s1, s2;
long long c[MAXN];

long long calc_initial_diff() {
    long long dragon = 0;
    long long tiger = 0;

    for (int i = 1; i <= n; i++) {
        if (i < m) {
            dragon += c[i] * (m - i);
        }
        else if (i > m) {
            tiger += c[i] * (i - m);
        }
    }

    if (p1 < m) {
        dragon += s1 * (m - p1);
    }
    else if (p1 > m) {
        tiger += s1 * (p1 - m);
    }

    return dragon - tiger;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    cin >> m >> p1 >> s1 >> s2;

    long long diff = calc_initial_diff();
    long long best_abs = -1;

    p2_ans = 1;
    for (int p2 = 1; p2 <= n; p2++) {
        long long new_diff = diff;

        if (p2 < m) {
            new_diff += s2 * (m - p2);
        }
        else if (p2 > m) {
            new_diff -= s2 * (p2 - m);
        }

        long long cur_abs = llabs(new_diff);
        if (best_abs == -1 || cur_abs < best_abs ||
            (cur_abs == best_abs && p2 < p2_ans)) {
            best_abs = cur_abs;
            p2_ans = p2;
        }
    }

    cout << p2_ans << '\n';

    return 0;
}

复杂度

先统计一次原始气势，再枚举所有 p2。

时间复杂度是 $O(n)$ ，空间复杂度是 $O(1)$ 。

总结

这题的关键是把“第二次投放后的总气势”看成对初始差值 diff 的一次简单修正。

一旦把这个关系写出来，枚举位置就够了。

P5016 [NOIP 2018 普及组] 龙虎斗

题目背景

NOIP2018 普及组 T2

题目描述

轩轩和凯凯正在玩一款叫《龙虎斗》的游戏，游戏的棋盘是一条线段，线段上有 $n$ 个兵营（自左至右编号 $1 \sim n$ ），相邻编号的兵营之间相隔 $1$ 厘米，即棋盘为长度为 $n-1$ 厘米的线段。 $i$ 号兵营里有 $c_i$ 位工兵。下面图 1 为 $n=6$ 的示例：

轩轩在左侧，代表“龙”；凯凯在右侧，代表“虎”。他们以 $m$ 号兵营作为分界，靠左的工兵属于龙势力，靠右的工兵属于虎势力，而第 $m$ 号兵营中的工兵很纠结，他们不属于任何一方。

一个兵营的气势为：该兵营中的工兵数$ \times $ 该兵营到 $m$ 号兵营的距离；参与游戏一方的势力定义为：属于这一方所有兵营的气势之和。
下面图 2 为 $n = 6,m = 4$ 的示例，其中红色为龙方，黄色为虎方：

游戏过程中，某一刻天降神兵，共有 $s_1$ 位工兵突然出现在了 $p_1$ 号兵营。作为轩轩和凯凯的朋友，你知道如果龙虎双方气势差距太悬殊，轩轩和凯凯就不愿意继续玩下去了。为了让游戏继续，你需要选择一个兵营 $p_2$ ，并将你手里的 $s_2$ 位工兵全部派往兵营 $p_2$ ，使得双方气势差距尽可能小。

注意：你手中的工兵落在哪个兵营，就和该兵营中其他工兵有相同的势力归属（如果落在 $m$ 号兵营，则不属于任何势力）。

输入格式

输入文件的第一行包含一个正整数 $n$ ，代表兵营的数量。

接下来的一行包含 $n$ 个正整数，相邻两数之间以一个空格分隔，第 $i$ 个正整数代表编号为 $i$ 的兵营中起始时的工兵数量 $c_i$ 。

接下来的一行包含四个正整数，相邻两数间以一个空格分隔，分别代表 $m,p_1,s_1,s_2$ 。

输出格式

输出文件有一行，包含一个正整数，即 $p_2$ ，表示你选择的兵营编号。如果存在多个编号同时满足最优，取最小的编号。

输入输出样例 #1

输入 #1

text

1
2
36 
2 3 2 3 2 3 
4 6 5 2

输出 #1

text

输入输出样例 #2

输入 #2

text

1
2
36 
1 1 1 1 1 16 
5 4 1 1

输出 #2

text

说明/提示

样例 1 说明

见问题描述中的图 2。
双方以 $m=4$ 号兵营分界，有 $s_1=5$ 位工兵突然出现在 $p_1=6$ 号兵营。龙方的气势为：

2 \times (4-1)+3 \times (4-2)+2 \times (4-3) = 14

虎方的气势为：

2 \times (5 - 4) + (3 + 5) \times (6 - 4) = 18

当你将手中的

s_2 = 2

位工兵派往

p_2 = 2

号兵营时，龙方的气势变为：

14 + 2 \times (4 - 2) = 18

此时双方气势相等。

样例 2 说明

双方以 $m = 5$ 号兵营分界，有 $s_1 = 1$ 位工兵突然出现在 $p_1 = 4$ 号兵营。
龙方的气势为：

1 \times (5 - 1) + 1 \times (5 - 2) + 1 \times (5 - 3) + (1 + 1) \times (5 - 4) = 11

虎方的气势为：

16 \times (6 - 5) = 16

当你将手中的

s_2 = 1

位工兵派往

p_2 = 1

号兵营时，龙方的气势变为：

11 + 1 \times (5 - 1) = 15

此时可以使双方气势的差距最小。

数据规模与约定

$1 < m < n$ ， $1 \le p_1 \le n$ 。
对于 $20\%$ 的数据， $n = 3,m = 2, c_i = 1, s_1,s_2 ≤ 100$ 。
另有 $20\%$ 的数据， $n ≤ 10, p_1 = m, c_i = 1, s_1,s_2 ≤ 100$ 。
对于 $60\%$ 的数据， $n ≤ 100, c_i = 1, s_1,s_2 ≤ 100$ 。
对于 $80\%$ 的数据， $n ≤ 100, c_i,s_1,s_2 ≤ 100$ 。
对于 $100\%$ 的数据， $n≤10^5$ , $c_i,s_1,s_2≤10^9$ 。

[NOIP 2018 普及组] 龙虎斗

目录

题意

思路

代码

复杂度

总结