天天看點

NOIP2018 c++普及組第2題-------龍虎鬥

時間限制: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的示例:

NOIP2018 c++普及組第2題-------龍虎鬥

軒軒在左側,代表“龍”;凱凱在右側,代表“虎”。 他們以 m 号兵營作為分界, 靠左的工兵屬于龍勢力,靠右的工兵屬于虎勢力,而第 ? 号兵營中的工兵很糾結,他 們不屬于任何一方。

一個兵營的氣勢為:該兵營中的工兵數 × 該兵營到 m 号兵營的距離;參與遊戲 一方的勢力定義為:屬于這一方所有兵營的氣勢之和。

下面圖 2 為 n = 6, m = 4 的示例,其中紅色為龍方,黃色為虎方:

NOIP2018 c++普及組第2題-------龍虎鬥

遊戲過程中,某一刻天降神兵,共有 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;
}

           

繼續閱讀