复赛二：龙虎斗(flight)

信息学奥赛历年真题 2018年NOIP普及组真题复赛二：龙虎斗(flight)

洛谷：P5016
OJ： P4960

解题思路：

题目要求在已有的兵营布局和工兵数量基础上，通过向某个兵营派遣s2个工兵，尽量平衡“龙”与“虎”双方的气势差。具体步骤如下：

读取输入数据：
- n：兵营的总数量。
- c[1..n]：每个兵营中初始的工兵数量。
- m：分界兵营编号，左侧属于“龙”势力，右侧属于“虎”势力，m号兵营中的工兵不属于任何一方。
- p1、s1：s1个工兵被天降到p1号兵营。
- s2：需要选择一个兵营p2，将s2个工兵派往该兵营。
更新p1号兵营的工兵数量：
- 将s1个工兵添加到p1号兵营，更新其工兵数量。
计算初始的“龙”与“虎”双方的气势：
- 龙方气势（lPower）： 对于所有编号小于m的兵营，计算气势贡献为c[i] * (m - i)，并累加得到龙方总气势。
- 虎方气势（rPower）： 对于所有编号大于m的兵营，计算气势贡献为c[i] * (i - m)，并累加得到虎方总气势。
- 中立兵营： 编号为m的兵营中的工兵不计入任何一方的气势。
计算当前的气势差：
- gap = abs(lPower - rPower)，表示当前“龙”与“虎”双方的气势差。
选择最佳的p2位置：
- 默认选择： 将s2个工兵放在中立的m号兵营，此时气势差保持不变。
- 遍历所有兵营：
  - 左侧兵营（i < m）： 如果将s2个工兵放在i号兵营，龙方气势增加s2 * (m - i)，计算新的气势差abs((lPower + s2 * (m - i)) - rPower)。
  - 右侧兵营（i > m）： 如果将s2个工兵放在i号兵营，虎方气势增加s2 * (i - m)，计算新的气势差abs((rPower + s2 * (i - m)) - lPower)。
  - 中立兵营（i == m）： 将工兵放在中立兵营不会改变气势差。
- 更新最佳p2位置： 选择能够使气势差最小化的兵营编号。如果存在多个兵营使得气势差相同，选择编号最小的兵营。
输出结果：
- 输出选择的最佳兵营编号p2，使得在派遣s2个工兵后，“龙”与“虎”双方的气势差最小。

代码实现：

/**************************************************************** 
 * Description: 2018年普及组第二题  龙虎斗
 * Author: Alex Li
 * Date: 2024-09-24 13:07:48
 * LastEditTime: 2024-10-02 11:20:31
****************************************************************/

#include <iostream>
#include <vector>
#include <cmath>
#include <limits>

using namespace std;

#define LL long long

int main(){
    // 打开输入输出文件
    freopen("fight.in","r",stdin);
    freopen("fight.out","w",stdout);
    
    int n, i, m, p1, p2;
    cin >> n; // 读取兵营数量
    
    LL c[n + 1], s1, s2; // c[1..n]存储每个兵营的工兵数量，s1和s2分别是天降神兵的数量
    for(i = 1; i <= n; i++){
        cin >> c[i]; // 读取每个兵营的初始工兵数量
    }
    
    cin >> m >> p1 >> s1 >> s2; // 读取分界兵营m，神兵出现的兵营p1，s1和s2的数量
    
    c[p1] += s1; // 将s1个工兵添加到p1号兵营
    
    LL lPower = 0; // 龙方总气势
    for(i = 1; i < m; i++) {
        lPower += c[i] * (m - i); // 计算左侧（龙方）各兵营的气势贡献
    }

    LL rPower = 0; // 虎方总气势
    for(i = m + 1; i <= n; i++) {
        rPower += c[i] * (i - m); // 计算右侧（虎方）各兵营的气势贡献
    }
    
    LL gap = abs(lPower - rPower); // 计算当前双方的气势差
    
    p2 = m; // 默认将s2个工兵放在中立的m号兵营

    // 遍历所有兵营，选择最优的p2位置
    for(i = 1; i <= n; i++){
        if(i < m){ // 如果选择将s2个工兵放在左侧（龙方）的某个兵营
            // 计算将s2个工兵放在i号兵营后，新的气势差
            LL newLPower = lPower + s2 * (m - i);
            LL newGap = abs(newLPower - rPower);
            if(newGap < gap){
                gap = newGap; // 更新最小气势差
                p2 = i; // 更新最佳p2位置
            }
        }
        else if(i > m){ // 如果选择将s2个工兵放在右侧（虎方）的某个兵营
            // 计算将s2个工兵放在i号兵营后，新的气势差
            LL newRPower = rPower + (i - m) * s2;
            LL newGap = abs(newRPower - lPower);
            if(newGap < gap){
                gap = newGap; // 更新最小气势差
                p2 = i; // 更新最佳p2位置
            }
        }
        // 如果i == m，则s2个工兵放在中立兵营，气势差保持不变，不需要更新
    }
    
    cout << p2 << endl; // 输出最佳的p2位置
    return 0;
}

Previous Topic

Back to Lesson

Next Topic