iT邦幫忙

0

拜託幫忙解這題C++

c++

英雄里其實剛好就是一條長長~的街道(又稱屠龍道),街道上居住了 N 戶人家,2020年又逢里長重新選舉,由於里長要負責對每一戶通知重要的消息,或處理相關的事務,來回奔波,太過勞累,因此今年英雄里的居民決定選出一位適合的里民做為里長,條件是這位里民在屠龍道上的居住地點與所有里民住所的相隔距離總和為最小,聰明的你寫個程式幫忙找出最適當的位置,並算出最小距離和為何?
<例>
N=4
-3 -1 0 8
選擇 -1 => 最小距離和為 [(-1) - (-3)] + [0 - (-1)] + [8 - (-1)] = 12
選擇 0 => 最小距離和為 [0 - (-3)] + [0 - (-1)] + [8 - 0] = 12
https://ithelp.ithome.com.tw/upload/images/20200518/20127206QZJHRNJ12a.jpg

看更多先前的討論...收起先前的討論...
dragonH iT邦超人 7 級 ‧ 2020-05-18 16:53:56 檢舉
https://ithelp.ithome.com.tw/questions/10198492

問她

他寫到 53 題了
通靈亡 iT邦新手 3 級 ‧ 2020-05-18 17:07:56 檢舉
可是這邊沒有屠龍道只有屠豬士
2020年好像只有里長補選………此題無解。
柯柯 iT邦新手 5 級 ‧ 2020-05-18 17:32:28 檢舉
也許還會有市長補選 ................不要出征我
dragonH iT邦超人 7 級 ‧ 2020-05-18 17:38:04 檢舉
樓上勇者
里長其實是黑手黨Vito
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=982
0
海綿寶寶
iT邦大神 1 級 ‧ 2020-05-19 08:53:47
#include <iostream>
#include <string>

using namespace std;

int partition(int A[],int l,int u)
{
    int i;
    i = l-1;
    for(int j=l;j<u;j++)
    {
        if(A[j] < A[u])
        {
            i++;
            swap(A[i],A[j]);
        }
    }
    i++;
    swap(A[i],A[u]);
    return i;
}

void quicksort(int A[],int a,int b)
{
    if(a < b)
    {
        int q;
        q = partition(A,a,b);
        quicksort(A,a,q-1);
        quicksort(A,q+1,b);
    }
}

void w040() {
    char sTimes[6];
    long int iTimes;
    char d[100000][10];
    int n[100000];
    int nMid;
    long int nSum = 0;
    
    cin >> sTimes;
    iTimes = atoi(sTimes);
    
    for (int i=0; i<iTimes; i++) {
        cin >> d[i];
        n[i] = atoi(d[i]);
    }

    quicksort(n, 0, iTimes-1);
    
    if (iTimes%2==0) {  //Even
        nMid = iTimes / 2;
    } else {            //Odd
        nMid = (iTimes-1) / 2 + 1;
    }
    
    for (long int i=0;i<iTimes;i++) {
        if (i<nMid) {
            nSum += n[nMid] - n[i];
        }
        else if (i>nMid) {
            nSum += n[i] - n[nMid];
        }
        else if (i==nMid) {
            //do nothing
        }
    }

    cout << nSum;
}

int main()
{
    w040();
    return 0;
}
0

沒有用到個數n,測試運行時間不到一秒,如果N的個數不是偶數要做個小修正,這部分你自己想吧
https://ithelp.ithome.com.tw/upload/images/20200522/20127325ObvVzK9jhq.jpg

0
賽門
iT邦超人 1 級 ‧ 2020-05-22 15:19:07

只有遠傳,沒有距離。
什麼時代了,還要用走路工。
看到這題,想到新冠肺炎病毒,大陸嚴格實施隔離,幹事(大陸沒有里長, 有各級幹事)通知事情都用微信。

我要發表回答

立即登入回答