お菓子の合併(欲張り+優先列)
C-結合果実
Crawling in process…
Crawling failed
Time Limit:1000 MS Memory Limit:13137172 KB 64 bit IO Format:%lld&%ll u
スーパースター
Description
今はn山の果物があります.i番目の山にai個の果物があります.今はこれらの果実を一つの山にまとめます.毎回の合併の価格は二つの果物の総果実数です.すべての果実の最小価格を統合することを求めます.
Input
最初の行は整数T(T<=50)を含み、データのグループ数を表します.各グループのデータの最初の行は、1つの整数n(2<==n==1000)を含み、果実の山の数を表しています.2行目はn個の正の整数ai(ai<=100)を含み、果物の山ごとの数を表します.
Output
各グループのデータは1行のみで、最小のマージ価格を表します.
Sample Input
Crawling in process…
Crawling failed
Time Limit:1000 MS Memory Limit:13137172 KB 64 bit IO Format:%lld&%ll u
スーパースター
Description
今はn山の果物があります.i番目の山にai個の果物があります.今はこれらの果実を一つの山にまとめます.毎回の合併の価格は二つの果物の総果実数です.すべての果実の最小価格を統合することを求めます.
Input
最初の行は整数T(T<=50)を含み、データのグループ数を表します.各グループのデータの最初の行は、1つの整数n(2<==n==1000)を含み、果実の山の数を表しています.2行目はn個の正の整数ai(ai<=100)を含み、果物の山ごとの数を表します.
Output
各グループのデータは1行のみで、最小のマージ価格を表します.
Sample Input
Sample Output2 4 1 2 3 4 5 3 5 2 1 4
ベント19 33
優先列の応用は、実際にはハフマンアルゴリズムに相当しています.最小の二つの山を取って統合し、統合後の山を同じ大きさで比較します.優先キューについては、参照できます.http://blog.csdn.net/qq_3076791/articale/detail/50569241優先列を使って問題をするのは初めてです.二つの点に注意が必要です.#include
#include #include using namespace std; int main() { int t,n,a; scanf("%d",&t); while(t--) { priority_queue ,greater >q; scanf("%d",&n); for(int i=0; i =2) { tmp=0; tmp+=q.top(); q.pop(); tmp+=q.top(); q.pop(); ans+=tmp; q.push(tmp); } printf("%d
",ans); } return 0; }【1】priority_queue
,greater >q; >> ; 【2】 q.top(), q.front()。