题解：P5016 [NOIP2018 普及组] 龙虎斗

· · 题解

题目传送门

题目大意

题目不难理解，先给了你一个 n 表示兵营的数量。\ 后面又给了每个兵营里起始的工兵数量。\ 以及一个兵营编号 m 表示中立兵营的编号。\ 还有三个数 p_1,s_1,s_2 分别表示天降神兵的位置，数量，第二次派兵的数量。\ 让你求你手上的兵放在哪个位置可以使两个兵营中的势力差更小。

做法

首先，我们可以提前求一遍实力差。\ 以此减小时间复杂度。\ 如果是暴力的算法，每一次都要求一遍势力差，放在这一题的数据就过不了。\ 所以提前求完之后，更新一下天降神兵后的势力差。\ 此时，用到一个变量 k 用于记录你手上的兵放在哪个兵营比较合适。\ 这里有个坑，k 的初始值应为 1，否则第二个点就会错。\ 因为如果初始化为 0，当没有找到任何一个点的势力差小于之前统计过的势力差，就会输出 0，但很明显，此时应输出 1。\ 这样只要更新一遍，就可以大大减小时间复杂度。

#include<bits/stdc++.h>
using namespace std;
int sum, s1, s2;
int c[100010];
int n, m, p1, p2, tmp;
int main() {
    // 优化
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    // 先照常输入
    cin >> n;
    for(int i=1; i<=n; i++) cin >> c[i];
    cin >> m >> p1 >> s1 >> s2;
    // 龙虎势力的差距
    // 原理：当 i < m  时  sum里的就是龙势力的总势力
    //       当 i == m 时  sum里没有改变  因为 m - i = 0
    //       当 i > m  时  sum每一次加的都是负数 算完之后就可以求出龙虎势力差
    for(int i=1; i<=n; i++) sum += ((m - i) * c[i]);
    // 求出p1兵营的势力
    sum += (m - p1) * s1;
    // 先算势力差
    long long cha = abs(sum + (m - 1) * s2);
    // k表示放到哪一个兵营
    int k = 1;
    // 后面每一次都算一次势力差
    for(int i=2; i<=n; i++) {
        // 继续算势力差
        tmp = abs(sum + ((m - i) * s2));
        // tmp 与 cha 比较 更新最小值
        if(tmp < cha) {
            // 取最小值
            cha = tmp;
            // 调整编号
            k = i;
        }
    }
    // 输出编号
    cout << k << '\n';
    return 0;
}

恭喜你，这一份是不对的。\ 你只要认真算后，就可以发现，要开 long long。

AC Code:

#include<bits/stdc++.h>
using namespace std;
long long sum, s1, s2;
long long c[100010];
long long n, m, p1, p2, tmp;
int main() {
    // 优化
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    // 先照常输入
    cin >> n;
    for(int i=1; i<=n; i++) cin >> c[i];
    cin >> m >> p1 >> s1 >> s2;
    // 龙虎势力的差距
    // 原理：当 i < m  时  sum里的就是龙势力的总势力
    //       当 i == m 时  sum里没有改变  因为 m - i = 0
    //       当 i > m  时  sum每一次加的都是负数 算完之后就可以求出龙虎势力差
    for(int i=1; i<=n; i++) sum += ((m - i) * c[i]);
    // 求出p1兵营的势力
    sum += (m - p1) * s1;
    // 先算势力差
    long long cha = abs(sum + (m - 1) * s2);
    // k表示放到哪一个兵营
    int k = 1;
    // 后面每一次都算一次势力差
    for(int i=2; i<=n; i++) {
        // 继续算势力差
        tmp = abs(sum + ((m - i) * s2));
        // tmp 与 cha 比较 更新最小值
        if(tmp < cha) {
            // 取最小值
            cha = tmp;
            // 调整编号
            k = i;
        }
    }
    // 输出编号
    cout << k << '\n';
    return 0;
}