当前位置：首页 > article >正文

信奥赛CSP-J复赛集训（模拟算法专题）（27）：P5016 [NOIP 2018 普及组] 龙虎斗

article 2025/3/25 19:01:38

信奥赛CSP-J复赛集训（模拟算法专题）（27）：P5016 [NOIP 2018 普及组] 龙虎斗

在这里插入图片描述

题目背景

NOIP2018 普及组 T2

题目描述

轩轩和凯凯正在玩一款叫《龙虎斗》的游戏，游戏的棋盘是一条线段，线段上有 $n$ 个兵营（自左至右编号 $\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

6 
2 3 2 3 2 3 
4 6 5 2

输出 #1

输入输出样例 #2

输入 #2

6 
1 1 1 1 1 16 
5 4 1 1

输出 #2

说明/提示

样例 1 说明

见问题描述中的图 2。
双方以 $m = 4$ 号兵营分界，有 $s_1=5$ 位工兵突然出现在 $p_1=6$ 号兵营。
龙方的气势为：
$\times (4-1)+3 \times (4-2)+2 \times (4-3) = 14$
虎方的气势为：
$\times (5 - 4) + (3 + 5) \times (6 - 4) = 18$
当你将手中的 $s_2 = 2$ 位工兵派往 $p_2 = 2$ 号兵营时，龙方的气势变为：
$\times (4 - 2) = 18$
此时双方气势相等。

样例 2 说明

双方以 $m = 5$ 号兵营分界，有 $s_1 = 1$ 位工兵突然出现在 $p_1 = 4$ 号兵营。
龙方的气势为：
$\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 \times (5 - 1) = 15$
此时可以使双方气势的差距最小。

数据规模与约定

$1 < m < n$ ， $\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$ 。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;  // 定义最大可能的数组大小
long long n, c[N];        // n为总位置数，c数组存储每个位置的初始兵力
long long m, p1, p2, s1, s2; // m为分界点，p1/s1为第一次事件的位置和兵力，s2为第二次事件的兵力，p2为待确定的最佳位置
long long dragon, tiger;  // 分别表示龙方和虎方的总势力值

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> c[i];  // 输入每个位置的初始兵力
    cin >> m >> p1 >> s1 >> s2;  // 输入分界点m，第一次事件的位置p1和兵力s1，以及第二次事件的兵力s2

    // 计算初始龙方和虎方的势力
    for(int i = 1; i <= n; i++){
        if(i < m) dragon += (m - i) * c[i];  // 龙方：位置i距离m越远，贡献越大
        if(i > m) tiger += (i - m) * c[i];   // 虎方同理
    }

    // 处理第一次事件，将s1加入对应阵营的势力
    if(p1 < m) dragon += (m - p1) * s1;  // p1在龙方区域
    if(p1 > m) tiger += (p1 - m) * s1;   // p1在虎方区域

    long long now = abs(dragon - tiger); // 当前两方势力差的绝对值
    p2 = m; // 初始化最佳位置为分界点m（默认情况）

    // 根据当前势力情况选择最佳策略
    if(dragon < tiger) {  // 龙方势力较弱，尝试在龙方区域添加s2以增强势力
        for(int i = 1; i <= m-1; i++) {
            long long new_dragon = dragon + (m - i) * s2; // 假设在i位置添加s2后的龙方新势力
            if(abs(new_dragon - tiger) < now) {  // 检查是否缩小差距
                now = abs(new_dragon - tiger);   // 更新最小差距
                p2 = i;                          // 更新最佳位置
            }
        }
    } else if(dragon > tiger) {  // 虎方势力较弱，尝试在虎方区域添加s2
        for(int i = m+1; i <= n; i++) {
            long long new_tiger = tiger + (i - m) * s2; // 假设在i位置添加s2后的虎方新势力
            if(abs(dragon - new_tiger) < now) {  // 检查是否缩小差距
                now = abs(dragon - new_tiger);
                p2 = i;
            }
        }
    }
    cout << p2;  // 输出最佳位置
    return 0;
}

功能分析：

输入处理
- 读取总位置数n和各位置初始兵力c[]。
- 读取分界点m、第一次事件参数p1和s1、第二次事件兵力s2。
势力计算
- 遍历所有位置，根据距离分界点m的远近，分别累加龙方（i < m）和虎方（i > m）的初始势力。
- 势力计算公式：每个位置的贡献 = 兵力 × 到分界点的距离（例如龙方：(m - i) * c[i]）。
处理第一次事件
- 根据p1的位置，将s1的兵力加入对应阵营的势力中，计算方式与初始势力相同。
寻找最佳位置p2
- 计算当前势力差now，并默认将s2放在分界点m（此时不影响双方势力）。
- 龙方较弱时：遍历龙方区域（1 ≤ i ≤ m-1），计算在i位置添加s2后的新势力差，记录最小差对应的位置。
- 虎方较弱时：遍历虎方区域（m+1 ≤ i ≤ n），同理寻找最优位置。
输出结果
- 输出使双方势力差最小的位置p2，若存在多个最优解，选择最先找到的最小差位置。