Mishka and trip(CodeForces - 703B)

題目描述：

Little Mishka is a great traveller and she visited many countries. After thinking about where to travel this time, she chose XXX — beautiful, but little-known northern country.

Here are some interesting facts about XXX:

1. XXX consists of n cities, k of whose (just imagine!) are capital cities.
2. All of cities in the country are beautiful, but each is beautiful in its own way. Beauty value of i-th city equals to ci.
3. All the cities are consecutively connected by the roads, including 1-st and n-th city, forming a cyclic route 1?—?2?—?...?—?n?—?1. Formally, for every 1?≤?i?<?n there is a road between i-th and i?+?1-th city, and another one between 1-st and n-th city.
4. Each capital city is connected with each other city directly by the roads. Formally, if city x is a capital city, then for every 1?≤?i?≤?n,??i?≠?x, there is a road between cities x and i.
   There is at most one road between any two cities.

Price of passing a road directly depends on beauty values of cities it connects. Thus if there is a road between cities i and j, price of passing it equals ci·cj.
Mishka started to gather her things for a trip, but didn't still decide which route to follow and thus she asked you to help her determine summary price of passing each of the roads in XXX. Formally, for every pair of cities a and b (a?<?b), such that there is a road between a and b you are to find sum of products ca·cb. Will you help her?

翻譯一下：

小MishKa是一個(gè)很棒的旅行家，她游覽過(guò)許多國(guó)家。在仔細(xì)想了一下這次該去哪玩之后，她選擇去XXX——一個(gè)美麗，但很小眾的北部國(guó)家。
這是她選擇這個(gè)國(guó)家的原因——一些有趣的事實(shí)：

1. XXX擁有n座城市，其中有k座作為省會(huì)城市。
2. 這個(gè)國(guó)家所有的城市都很美麗，但是每一個(gè)美麗的城市都有她的獨(dú)特之處。她特地為每個(gè)城市設(shè)置了一個(gè)“美麗值”，第i座城市的“美麗值”為ci
3. 每座城市都被許多條道路連接著，從第一座城市到第二座城市，再?gòu)牡诙鞘械降谌鞘小購(gòu)牡趎座城市到第1座城市，組成了一個(gè)環(huán)行路（1-2-3……-n-1）。正式地，對(duì)于每一座城市（1 <= i <=n），在第i和第i+1座城市之間會(huì)有一條路，另外還有一條路在第n和第一條路之間。
4. 每一座省會(huì)城市都與其他的所有城市有且僅有一條路連接，正式的，如果x城市是省會(huì)城市，那么對(duì)于除它之外的所有城市（1 <= i <= n,i ≠ x）,都會(huì)有一條路在它們(i,x)之間。

通過(guò)一條路的過(guò)路費(fèi)只取決于這條路所連接的兩座城市的魅力值。因此如果在城市i和城市j之間有一條路，那么它的過(guò)路費(fèi)為ci*cj。

Mishka已經(jīng)開(kāi)始整理行裝，但她仍未決定如何選擇路線(xiàn)，所以她想讓你幫她算出XXX國(guó)家所有道路的過(guò)路費(fèi)之和。。（既然有第四條下邊那句話(huà)，后邊那段文字不知道還有何存在的意義。。除了迷惑我。。。。）

輸入

The first line of the input contains two integers n and k (3?≤?n?≤?100?000,?1?≤?k?≤?n) — the number of cities in XXX and the number of capital cities among them.
The second line of the input contains n integers c1,?c2,?...,?cn (1?≤?ci?≤?10?000) — beauty values of the cities.
The third line of the input contains k distinct integers id1,?id2,?...,?idk (1?≤?idi?≤?n) — indices of capital cities. Indices are given in ascending order.

翻譯一下：

第一行是兩個(gè)整數(shù)n(3 <= n <= 100000)和k(1 <= k <= n)——XXX國(guó)家的所有城市及省會(huì)城市的個(gè)數(shù)。
第二行是n個(gè)整數(shù)c1、c2、……、cn(1 <= ci <= 10000)——每座城市的美麗值。
第三行是k個(gè)確切的整數(shù)值id1、id2、……、idk(1 <= idi <= n)——每座省會(huì)城市在所有城市集合里的序號(hào)。

輸出

Print the only integer — summary price of passing each of the roads in XXX.

翻譯一下

只輸出唯一的一個(gè)整數(shù)——XXX國(guó)家的所有道路的過(guò)路費(fèi)之和

題目小貼士

This image describes first sample case:

It is easy to see that summary price is equal to 17.

This image describes second sample case:
![題目小貼士][1]

It is easy to see that summary price is equal to 71.

第一次嘗試

一開(kāi)始做的思路：先設(shè)置省會(huì)數(shù)組，用于區(qū)分普通城市和省會(huì)城市，再對(duì)所有城市進(jìn)行遍歷。遍歷過(guò)程中，若當(dāng)前城市為省會(huì)，則計(jì)算所有與其相連道路的過(guò)路費(fèi)（不包括在它之前遍歷到的省會(huì)與其之間的道路）；若為普通城市，當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)為頭結(jié)點(diǎn)，則計(jì)算當(dāng)前城市與頭節(jié)點(diǎn)之間路徑的過(guò)路費(fèi)，加入到總路徑中，否則計(jì)算當(dāng)前結(jié)點(diǎn)與下一個(gè)節(jié)點(diǎn)道路的過(guò)路費(fèi)，計(jì)算到總路徑中。
在代碼中用到了雙重循環(huán),時(shí)間復(fù)雜度為O(n2)，由于題目限制運(yùn)行時(shí)間是1000ms,粗略估計(jì)遍歷城市的循環(huán)最壞情況下會(huì)執(zhí)行10000*10000=100000000—，一億次。果然提交后題目報(bào)錯(cuò)：Time limit。

#include<stdio.h>
#include<stdlib.h>

#define N 100000

int main()
{
    int n, k;
    int c[N];
    int id[N];
    int sum = 0;
    int iflag;
    int cap[N] = { 0 };
    scanf("%d %d", &n, &k);
    for (int i = 1; i < n + 1; i++)             //初始化城市
    {
        scanf("%d", &c[i]);
    }
    for (int i = 1; i < k + 1; i++)
    {
        scanf("%d", &id[i]);
        cap[id[i]] = 1;
    }                                           //讀取省會(huì)城市個(gè)數(shù)

    for (int i = 1; i < n + 1; i++)
    {
        if (cap[i] == 1)
        {
            for (int j = 1; j < n + 1; j++)
            {
                if (j < i&&cap[j] == 1 || i == j)
                {
                    continue;
                }
                else
                {
                    sum += (c[i] * c[j]);
                }
            }
            continue;
        }
        if ((i + 1) % (n + 1) == 0)             //若下一個(gè)結(jié)點(diǎn)循環(huán)至頭結(jié)點(diǎn)
        {
            if (cap[(i + 2) % (n + 1)] != 1)    //若不為省會(huì)
            {
                sum += c[i] * c[1];
                continue;
            }
        }
        else if (cap[(i + 1) % (n + 1)] != 1)       //否則 若不為省會(huì)
        {
            sum += c[i] * c[(i + 1) % (n + 1)];
            continue;
        }
    }
    printf("%d", sum);
    return 0;
}

第二次嘗試

第二次嘗試消去二重循環(huán)，改變一種思路。設(shè)置了一些輔助變量。
可以先計(jì)算全部城市的美麗值之和作為help_sum，省會(huì)城市的美麗值之和作為help_sum2，再分別討論遍歷省會(huì)城市和普通城市的情況，若為省會(huì)城市，則只需計(jì)算其與所有城市的過(guò)路費(fèi)之和，再減去與省會(huì)城市多算的過(guò)路費(fèi)即為該省會(huì)城市所有未走過(guò)道路需交過(guò)路費(fèi)；若為普通城市，則判斷下個(gè)城市再?zèng)Q定是否交過(guò)路費(fèi)。
再次提交顯示wrong answer on test 10，原因?yàn)樵O(shè)置變量長(zhǎng)度太小。int的范圍為[-2^31, 2^31-1]即 [-2147483648,2147483647]，21億；long long 的范圍為 [-2^63, 2^63-1]即 [-9223372036854775807, 9223372036854775807]，100億億，更改大數(shù)據(jù)變量為long long后提交，代碼順利通過(guò)。 ^ ^
代碼如下：

#include<stdio.h>
#include<stdlib.h>

#define N 100004

int main()
{
    int n, k;
    int c[N];
    int *id;
    long long sum = 0;
    int *cap;
    long long help_sum = 0;
    long long help_sum2 = 0;
    scanf("%d %d", &n, &k);
    if (n<3 || k>n || k < 1)
        return 1;
    cap = (int *)malloc((n + 1) * sizeof(int));
    id = (int *)malloc((k + 1) * sizeof(int));
    for (int i = 1; i < n + 1; i++)             
    {
        scanf("%d", &c[i]);
        help_sum += c[i];
        cap[i] = 0;
    }
    for (int i = 1; i < k + 1; i++)
    {
        scanf("%d", &id[i]);
        cap[id[i]] = 1;
        help_sum2 += c[id[i]];
    }                                           

    for (int i = 1; i < k + 1; i++)
    {
        sum += ((help_sum - c[id[i]])*c[id[i]]);
        sum -= ((help_sum2 - c[id[i]])*c[id[i]]);
        help_sum2 -= c[id[i]];
    }
    for (int i = 1; i < n; i++)
    {
        if (cap[i] != 1 && cap[i + 1] != 1)
        {
            sum += c[i] * c[i + 1];
        }
    }
    if (cap[n] != 1 && cap[1] != 1)
    {
        sum += c[1] * c[n];
    }
    printf("%lld\n", sum);
    return 0;
}

小小總結(jié)

這也是一道很簡(jiǎn)單的題目，并沒(méi)有涉及復(fù)雜的數(shù)據(jù)結(jié)構(gòu)知識(shí)。
感覺(jué)該題不過(guò)是解法非常難想，各方面限制較多?；藢⒔胩斓臅r(shí)間（12個(gè)小時(shí)。。）做這么一道題目，從最開(kāi)始不斷地優(yōu)化時(shí)間復(fù)雜度，再到一個(gè)測(cè)試用例無(wú)法通過(guò)不斷檢查代碼，最終通過(guò)使用long long 擴(kuò)大了變量范圍才最終ac。真的是一次對(duì)意志力的小考驗(yàn)，差點(diǎn)就沒(méi)能堅(jiān)持到ac。所以以后寫(xiě)題目更要注意優(yōu)化代碼，盡量不要使用多重循環(huán)，數(shù)據(jù)如果過(guò)大則要使用范圍更大的數(shù)據(jù)類(lèi)型，更重要的是在以后的刷題路上一定要保持對(duì)自己的信心！
[1]: https://odzkskevi.qnssl.com/978f7393c18621d84fea150293a264cc?v=1485951373