NOIP 2018普及组复赛C++详细题解报告（2）

叁歲伎倆 2022-03-20 11:22 159阅读 0赞

# 第2题 龙虎斗 #

## 一、分析 ##

（1）ci最大值是10亿，n最大值是10万，相乘明显会超过INT\_MAX，所以本题要用long long才有可能得满分。若用int，最多只能得80分。  
（2）若能想到c是count的缩写，p是position的缩写，s是soldier的缩写，对理解题意会有所帮助。  
（3）p1和s1是个很弱的干扰项，直接加到该位置即可。

## 二、算法实现 ##

求气势差的最小值，有两种方法。  
第一种方法是暴力枚举，每移动一次，就判断气势差距是不是变得更小了。这种方法，最多可能要计算10万次。通常几百万内的循环不会运行超时。

方法一 完整代码

#include <iostream>
    #include <cstdio>
    #include <cmath>
    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;
        for(i = 1; i <= n; i++)
        {
            cin >> c[i];
        }
    
        cin >> m >> p1 >> s1 >> s2;
        c[p1] += s1;
    
        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);
        }
    
        //cout << lPower << ' ' << rPower << endl;
    
        LL gap = abs(lPower - rPower); // 双方的气势差
        p2 = m; //默认放在m位置
        for(i = 1; i <= n; i++)
        {
            if(i < m)   // 神兵加到左侧龙势力
            {
                if(abs(lPower + s2 * (m - i) - rPower) < gap)
                {
                    gap = abs(lPower + s2 * (m - i) - rPower);
                    p2 = i;
                }
            }
            else if(i > m) // 神兵加到右侧虎势力
            {
                if(abs(rPower + (i - m) * s2 - lPower) < gap)
                {
                    gap = abs(rPower + (i - m) * s2 - lPower);
                    p2 = i;
                }
            }
        }
        cout << p2 << endl;
    
        return 0;
    }

评测结果：

![2.png][]

第二种方法，用龙势力和虎势力的气势差除去s2，会得到s2离m号兵营的距离dist。注意dist不能定义为整数，只能定义为浮点数。当龙势力小于虎势力且距离中包含0.5时，要往左多挪一个位置，这样得到的p2与m的距离最大，从而p2取得最小值 ；当龙势力大于虎势力且距离中包含0.5时，0.5直接去掉，这样就不用往右再挪一个距离了。这样得到的p2与m的距离最小，从而p2取得最小值。  
举两个例子，这两个例子里不用考虑p1和s1，对理解题意影响不大。  
例1  
n = 3，c1 = 10, c3 = 11，c2等于随便一个数，比如1。m = 2。s2 = 2。  
在s2没放进去时，势力差gap = 虎势力 - 龙势力 = 1。dist = gap / s2 = 0.5，所以p2 = m – int(dist + 0.5) = 1，即要把s2放到1号营里。  
此时龙势力 = 10 + 2 = 12， 虎势力 = 11，gap仍然是1，但此时的p2最小。

例2  
n = 3，c1 = 11, c3 = 10，c2等于随便一个数，比如1。m = 2。s2 = 2。  
在s2没放进去时，势力差gap = 龙势力 – 虎势力 = 1。dist = gap / s2 = 0.5，所以p2 = m + ceil(dist -0.5) = m + 0 = m，即要把s2放到中立的m号营里。  
此时龙势力 = 11， 虎势力 = 10，m号营势力 = 1 + 2 = 3，gap仍然是1，此时的p2最小。

方法二完整代码

#include <iostream>
    #include <cmath>
    #include<cstdio>
    using namespace std;
    
    #define LL long long
    
    int main()
    {
        freopen("fight21.in","r",stdin);
    	freopen("fight.out","w",stdout);
        int n, i, m, p1, p2;
        LL s1, s2;
        cin >> n;
        LL c[n + 1];
        for(i = 1; i <= n; i++)
        {
            cin >> c[i];
        }
        cin >> m >> p1 >> s1 >> s2;
        c[p1] += s1;
    
        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);
        }
    
        //cout << lPower << ' ' << rPower << endl;
    
        LL gap = abs(lPower - rPower); // 双方的气势差
        p2 = m;          // 暂放在m的位置上
        float dist = gap * 1.0 / s2; // s2离m兵营的距离
        if(rPower > lPower)  // 虎势力大，s2要放在龙方
        {
            //这里floor()也可以改为int()
            p2 = m - floor(dist + 0.5);
            if(p2 < 1)
            {
                p2 = 1; // 不能越界
            }
        }
        else if(rPower < lPower)
        {
            // 注意，这里0.5是要舍弃掉的，大于0.5才加1
            p2 = m + ceil(dist - 0.5);
            if(p2 > n)
            {
                p2 = n; // 不能越界
            }
        }
    
        cout << p2 << endl;
    
        return 0;
    }

> 少儿编程咨询、算法咨询请加微信307591841或QQ群581357582  
> ![诺依曼算法公众号.jpg][.jpg]

[2.png]: /images/20220320/dda2bb85222e4b09a2896e057c9e3f02.png
[.jpg]: /images/20220320/19f38ba96b25448baabff818bc86149a.png

发表评论取消回复

表情：

评论列表（有 0 条评论，159人围观）

还没有评论，来说两句吧...

相关阅读

相关 NOIP 2009 普及组初赛试题解题报告、题解及选择题思路，高质量

[洛谷题目测试链接][Link 1] 单项选择题 <table> <thead> <tr> <th>1</th> <th>2</th>

心已赠人/ 2022年11月14日 10:17/ 0 赞/ 134 阅读

相关 NOIP 2016普及组复赛C/C++详细题解报告

第1题这题很简单，唯一需要注意的是需要判断能不能整除。 include <iostream> include <climits> includ

矫情吗；*/ 2022年05月15日 15:13/ 0 赞/ 274 阅读

相关 NOIP 2017普及组复赛C/C++详细题解报告

一、题目 https://wenku.baidu.com/view/f3fe5a326ad97f192279168884868762cbaebb71.html?from=

我会带着你远行/ 2022年05月08日 08:48/ 0 赞/ 428 阅读

相关 NOIP 2018普及组复赛第1题答案详解

![NOIP 2018普及组复赛第1题.jpg][NOIP 2018_1_.jpg] 一、C程序 \\\解法一：用gets()函数 include <stdi

我会带着你远行/ 2022年04月15日 04:56/ 0 赞/ 211 阅读

相关二进制分类 NOIP1995复赛普及组第三题

描述若将一个正整数化为二进制数，在此二进制数中，我们将数字1的个数多于数字0的个数的这类二进制数称为A类数，否则就称其为B类数。例如： (13)10 = (1101)

柔情只为你懂/ 2022年03月30日 10:16/ 0 赞/ 236 阅读

相关 NOIP 2018普及组复赛C++详细题解报告（2）

第2题龙虎斗一、分析（1）ci最大值是10亿，n最大值是10万，相乘明显会超过INT\_MAX，所以本题要用long long才有可能得满分。若用int，最多

叁歲伎倆/ 2022年03月20日 11:22/ 0 赞/ 160 阅读

相关 NOIP 2018普及组复赛C++详细题解报告（1）

第1题标题统计一、代码 include <iostream> include <cstdio> using namespace std;

红太狼/ 2022年03月20日 11:18/ 0 赞/ 196 阅读

相关 NOIP 2018普及组复赛C/C++参考答案

第1题标题统计 include <iostream> include <cstdio> using namespace std;

你的名字/ 2022年01月30日 13:25/ 0 赞/ 225 阅读

相关 NOIP2016普及组初赛部分题解

问题求解1：从一个 4×4 的棋盘（不可旋转）中选取不在同一行也不在同一列上的两个方格，共有\_\_\_\_72\_\_\_\_\_种方法。 ![watermark

川长思鸟来/ 2021年11月11日 10:04/ 0 赞/ 416 阅读

相关 NOIP真题题解-普及组（模拟一）

1. 陶陶摘苹果来源：NOIP2005普及组 [https://ac.nowcoder.com/acm/contest/233/A][https_ac.nowcode

一时失言乱红尘/ 2021年11月09日 10:16/ 0 赞/ 354 阅读