c223: Add All(變異版)
標籤 :
通過比率 : 26% (10 人 / 39 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2017-07-05 23:14

內容 :

是的,題目名稱就是你要做的任務:把一些數加起來。但是這對你來說一定是太簡單了,所以讓我們加一些東西在裡面。

做加法要付出的代價(cost) 定義為這2個數的總和,所以要加 1 和 10 所需付出的代價為 11 。假如你想要加 1, 2 和 3,那麼有以下幾種方法:

1 + 2 = 3, cost = 3
3 + 3 = 6, cost = 6
Total = 9

1 + 3 = 4, cost = 4
2 + 4 = 6, cost = 6
Total = 10

2 + 3 = 5, cost = 5
1 + 5 = 6, cost = 6
Total = 11

我希望你已經瞭解你的任務,就是把 N 個數加起來使得付出的代價最少。

...

等等!以為我會在ZJ上放一題一模一樣的題目嗎?

看啊這題都已經被放上來兩次了!(其實還有類似題,可是純搜尋找不到OwO)

現在加大 N 的範圍,你還能AC這題嗎?

輸入說明

輸入含有多組測試資料,不超過10筆測試資料。

每組測試資料開始有一個正整數 N(2 <= N <=106),接下來有 N 個正整數(均不超過106)。

 

當 N=0 時代表輸入結束。請參考Sample Input。

輸出說明

對每一組測試資料輸出一列,相加這N個數付出的代價最少是多少。

範例輸入
3
1 2 3
4
1 2 3 4
0
範例輸出
9
19
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <10M
公開 測資點#2 (59%): 2.0s , >50M
公開 測資點#3 (1%): 1.0s , >50M
提示 :

改自 Lucky貓

對於20%的測試資料 N<=10^3

對於40%的測試資料 N<=10^5

對於99%的測試資料 Time limit 2s

對於1%的測試資料 Time limit 1s

2017/7/6 23:09更新,因為被壓到1s內了OAO

標籤:
出處:
UVA [編輯:
pcshic (PCSHIC)
]
編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」