【題目鏈接】

ybt 1979： 【18NOIP普及組】龍虎斗
洛谷 P5016 [NOIP2018 普及組] 龍虎斗

【題目考點】

1. long long類型使用

已知變量a, b是int類型的變量，且a * b的值會超出int類型可以表示的范圍，如果寫為：long long c = a * b;，c不會得到正確的結果。正確的寫法為：long long c = (long long)a * b;
把一個變量強轉為long long類型后，后面的運算就是兩個long long類型的變量相乘，會得到正確的結果。例：

int a = 100000, b = 100000; long long c = (long long)a * b;//此時c的值為10^10

2. 求絕對值

<stdlib.h>中有
int abs(int a);
long labs(long a);
但沒有針對long long類型變量的求絕對值的函數，所以我們必須手動實現。

long long Abs(long long a) {return a > 0 ? a : -a; }

【解題思路】

• 先把s1個兵添加上去，然后求龍虎雙方的氣勢值。

• 枚舉每隔位置，嘗試將s2個兵添加到這個位置，求出氣勢差值。將每次求出的氣勢差值比較，得到最小的氣勢差值，以及氣勢差值最小時，將s2個兵安排的位置。

• 注意：觀看數據范圍，每個位置的工兵數最大為$10^9$，共有$10^5$個位置，加起來的氣勢和可以估算為$10^9?10^5=10^{14}$超出了int型變量可以表達的范圍，所以對某些變量要用long long類型
  某些int型量間的計算，如s2 * (m - i)，結果可能超出int型的范圍，所以得先強轉為long long類型后才能運算
  ，應寫為：(long long)s2 * (m - i)

【題解代碼】

解法1：分別求出龍方和虎方的氣勢

#include<bits/stdc++.h> using namespace std; #define N 100005 long long Abs(long long a) {return a > 0 ? a : -a; } int a[N];//a[i]表示第i位置的工兵數 int main() {int n, m, p1, s1, s2, p2;//p2：s2個兵放在p2位置時雙方差值最小long long ql = 0, qh = 0, mn, delta;//ql:龍方氣勢 qh:虎方氣勢 mn：兩方最小氣勢差值 delta:氣勢差值cin>>n;for(int i = 1; i <= n; ++i)cin>>a[i];cin>>m>>p1>>s1>>s2;a[p1] += s1;//天降神兵for(int i = 1; i < m; ++i)//統計當前龍方氣勢ql += (long long)a[i] * (m - i);for(int i = m + 1; i <= n; ++i)//統計當前虎方氣勢qh += (long long)a[i] * (i - m);mn = Abs(ql - qh);//雙方氣勢差值最大也就是當前的差值，s2個工兵放下后，氣勢差值只能更小p2 = m;//s2個兵放在第m位置時，氣勢差值即為|ql - qh|for(int i = 1; i <= n; ++i){if(i < m)delta = Abs(ql + (long long)s2 * (m - i) - qh);//向龍方i位置放s2個兵，龍方增加氣勢s2 * (m - i)。求此時龍虎雙方的氣勢差值。else if(i > m)delta = Abs(qh + (long long)s2 * (i - m) - ql);//向虎方i位置放s2個兵，虎方增加氣勢s2 * (i - m)。求此時龍虎雙方的氣勢差值。if(delta < mn)//求最小的delta，及delta最小時放兵的位置{mn = delta;p2 = i;}}cout<<p2;return 0; }

解法2：龍方氣勢是正數，虎方氣勢是負數

設置變量q表示雙方總氣勢，q > 0表示龍方氣勢高，q < 0表示虎方氣勢高，$|q|$就是雙方氣勢的差值

#include<bits/stdc++.h> using namespace std; #define N 100005 long long Abs(long long a) {return a > 0 ? a : -a; } int a[N];//a[i]表示第i位置的工兵數 int main() {int n, m, p1, s1, s2, p2;//p2：s2個兵放在p2位置時雙方差值最小long long q = 0, mn, delta;//q：總氣勢，q > 0表示龍方氣勢高，q < 0表示虎方氣勢高 mn：兩方最小氣勢差值 delta:氣勢差值cin>>n;for(int i = 1; i <= n; ++i)cin>>a[i];cin>>m>>p1>>s1>>s2;a[p1] += s1;//天降神兵for(int i = 1; i <= n; ++i)//統計總氣勢q += (long long)a[i] * (m - i);//龍方氣勢是正數，虎方氣勢是負數mn = Abs(q);//雙方氣勢差值最大也就是當前的差值，s2個工兵放下后，氣勢差值只能更小p2 = m;//s2個兵放在第m位置時，氣勢差值即為|q|for(int i = 1; i <= n; ++i){delta = Abs(q + (long long)s2 * (m - i));//向龍方i位置放s2個兵，總氣勢改變s2 * (m - i)。if(delta < mn)//求最小的delta，及delta最小時放兵的位置{mn = delta;p2 = i;}}cout<<p2;return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1979：【18NOIP普及组】龙虎斗 | 洛谷 P5016 [NOIP2018 普及组] 龙虎斗的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。