NOI 2.4分割7617:出力前kの大きさの数

1576 ワード

NOI

タイトルのソース:http://noi.openjudge.cn/ch0204/7617
7617:出力前kの大きさの数
総時間制限: 10000 ms 単体テストポイント時間制限:1000 ms メモリ制限: 65536 kB
説明
配列を与えて、前のkの大きい数を統計して、このk個の数を大から小出力にします.
入力
最初の行は整数nを含み、配列のサイズを表します.n<100000.2行目はn個の整数を含み、配列の要素を表し、整数の間は1つのスペースで区切られます.各整数の絶対値は100000万を超えません.3行目は整数kを含みます.k出力
大きいものから小さいものまで、前のkの大きさの数を、各ラインずつ数えます.
サンプル入力
104 5 6 9 8 7 1 2 3 5
サンプル出力
98765
------------------------------------------
問題を解く構想
最大の山
ビルドO(N)

make_heap(arr,arr+n);

最初の元素が沈んで、毎回O(logN)

pop_heap(arr,arr+n-i);

総複雑度O(N＋klogN)
直接pricetyを使えばqueueはO(NlogN)です.少し遅くなりますが、過ぎることもあります.
------------------------------------------
コード

//7617:   k   
//     : 10000ms          : 1000ms     : 65536kB
//  
//      ，   k       k        。
//
//  
//         n，       。n < 100000。
//     n   ，       ，           。           100000000。
//         k。k < n。
//  
//       k   ，     。
//    
//10
//4 5 6 9 8 7 1 2 3 0
//5
//    
//9
//8
//7
//6
//5

#include
#include
#include
#include
#include
using namespace std;

int arr[100000] = {};

int main()
{
#ifndef ONLINE_JUDGE
	ifstream fin("0204_7617.txt");
	int n,k,i;
	fin >> n;
	for (i=0; i> arr[i];
	}
	fin >> k;
	fin.close();
	make_heap(arr,arr+n);
	for (i=0; i

uuntu 14.04 Qt 5.5.1をインストールします.