時間限制:C/C++ 1秒,其他語言2秒
空間限制:C/C++ 262144K,其他語言524288K
64bit IO Format: %lld
題解:模拟即可,更新最小值,記下下标。
需要注意的是剛開始應該預設把士兵派到中立陣營,即s2=m。
因為即便是小于也有可能派出去使得雙方懸殊變大。
題目描述
軒軒和開開正在玩一款叫《龍虎鬥》的遊戲,遊戲的棋盤是一條線段,線段上有n個兵營(自左至右編号1~n),相鄰編号的兵營之間相隔1厘米,即棋盤為長度為n-1厘米的線段。i号兵營裡有ci位工兵。
下面圖1為n = 6的示例:
軒軒在左側,代表“龍”;凱凱在右側,代表“虎”。 他們以 m 号兵營作為分界, 靠左的工兵屬于龍勢力,靠右的工兵屬于虎勢力,而第 ? 号兵營中的工兵很糾結,他 們不屬于任何一方。
一個兵營的氣勢為:該兵營中的工兵數 × 該兵營到 m 号兵營的距離;參與遊戲 一方的勢力定義為:屬于這一方所有兵營的氣勢之和。
下面圖 2 為 n = 6, m = 4 的示例,其中紅色為龍方,黃色為虎方:
遊戲過程中,某一刻天降神兵,共有 s1 位工兵突然出現在了p1号兵營。作為軒軒和凱凱的朋友,你知道如果龍虎雙方氣勢差距太懸殊,軒軒和凱凱就不願意繼續玩下去了。為了讓遊戲繼續,你需要選擇一個兵營 p2,并将你手裡的 s2位工兵全部派往 兵營p2,使得雙方氣勢差距盡可能小。
注意:你手中的工兵落在哪個兵營,就和該兵營中其他工兵有相同的勢力歸屬(如果落在 m 号兵營,則不屬于任何勢力)。
輸入描述:
輸入檔案的第一行包含一個正整數 n,代表兵營的數量。
接下來的一行包含 n 個正整數,相鄰兩數之間以一個空格分隔,第 i 個正整數代表編号為 i 的兵營中起始時的工兵數量 ci。接下來的一行包含四個正整數,相鄰兩數間以一個空格分隔,分别代表 m, p1, s1, s2。
輸出描述:
輸出檔案有一行,包含一個正整數,即 p2,表示你選擇的兵營編号。如果存在多個編号同時滿足最優,取最小的編号。
輸入
6
2 3 2 3 2 3
4 6 5 2
輸出
2
說明
見問題描述中的圖 2。
雙方以 m=4 号兵營分界,有 S1 =5 位工兵突然出現在 P1 =6 号兵營。
龍方的氣勢為:
2 × (4 − 1) + 3 × (4 − 2) + 2 × (4 − 3) = 14
虎方的氣勢為:
當你将手中的 ?2 = 2 位工兵派往 P2 = 2 号兵營時,龍方的氣勢變為:
2 × (5 − 4) + (3 + 5) × (6 − 4) = 18 14 + 2 × (4 − 2) = 18
此時雙方氣勢相等。
雙方以 ?=5 号兵營分界,有 ?1 =1 位工兵突然出現在 P1 =4 号兵營。 龍方的氣勢為:
1 × (5 − 1) + 1 × (5 − 2) + 1 × (5 − 3) + (1 + 1) × (5 − 4) = 11
虎方的氣勢為:
16 × (6 − 5) = 16
當你将手中的 S2 = 1 位工兵派往 P2 = 1 号兵營時,龍方的氣勢變為:
11 + 1 × (5 − 1) = 15
此時可以使雙方氣勢的差距最小。
AC代碼
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
long long a[maxn];
int main(){
long long n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
long long m,p1,s1,s2;
cin>>m>>p1>>s1>>s2;
a[p1]+=s1;
long long sum1=0;
long long sum2=0;
for(int i=1;i<=m-1;i++)
sum1+=a[i]*(m-i);
for(int i=m+1;i<=n;i++)
sum2+=a[i]*(i-m);
long long minn=abs(sum1-sum2);
long long x=m;//即便是小于也有可能派出去使得雙方懸殊變大,剛開始派到中立派
if(sum1<sum2){//增加sum1;
for(int i=1;i<=m-1;i++){
long long temp=sum1+s2*abs(i-m);
if(abs(temp-sum2)<minn){
minn=abs(temp-sum2);
x=i;
}
}
}
else if(sum1>sum2){//增加sum2
for(int i=m+1;i<=n;i++){
long long temp=sum2+s2*abs(i-m);
if(abs(temp-sum1)<minn){
minn=abs(temp-sum1);
x=i;
}
}
}
else
x=m;
cout<<x<<endl;
return 0;
}