hdu--1280--与前类似

这题和我前天还是昨天做的一题很相似

都是先2层for预处理然后通过hash标记数组来做

这题我也尝试了下用优先队列

第一遍做的时候忘记在2层for里面去维护队列长度了导致MLE。。。

第2遍就过了但是速度上还是比hash慢点但多种做题的思路就够了~

　　　　　　touch me

 1 #include <iostream>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 
 6 struct cmp
 7 {
 8     bool operator()( int& a , int& b )
 9     {
10         return a>b;
11     }
12 };
13 priority_queue<int,vector<int>,cmp>q;
14 int arr[3010];
15 int main()
16 {
17     cin.sync_with_stdio(false);
18     int n , k , cnt;
19     bool flag;
20     while( cin >> n >> k )
21     {
22         while( !q.empty() )
23             q.pop();
24         cnt = 0;
25         for( int i = 0 ; i<n ; i++ )
26         {
27             cin >> arr[i];
28             for( int j = 0 ; j<i ; j++ )
29             {
30                 cnt++;
31                 q.push(arr[i]+arr[j]);
32                 if(cnt>k)
33                 {
34                     q.pop();
35                 }
36             }
37         }
38         cnt = 0;
39         while( !q.empty() )
40         {
41             arr[cnt++] = q.top();
42             q.pop();
43         } 
44         for( int i = cnt-1; i>=1 ; i-- )
45         {
46             cout << arr[i] << " ";
47         }
48         cout << arr[0] << endl;
49     }
50     return 0;
51 }

View Code

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 int hash[10010];
 6 int arr[3010];
 7 int main()
 8 {
 9     cin.sync_with_stdio(false);
10     int n , k , cnt;
11     bool flag;
12     while( cin >> n >> k )
13     {
14         flag = false;
15         memset( hash , 0 , sizeof(hash) );
16         cnt = 0;
17         for( int i = 0 ; i<n ; i++ )
18         {
19             cin >> arr[i];
20             for( int j = 0 ; j<i ; j++ )
21             {
22                 hash[ arr[i] + arr[j] ]++;
23             }
24         }
25         for( int i = 10000; i>=0 ; i-- )
26         {
27             while( hash[i]-- )
28             {
29                 cnt++;
30                 if( cnt == k )
31                 {
32                     cout << i << endl;
33                     flag = true;
34                     break;
35                 }
36                 else
37                 {
38                     cout << i << " ";
39                 }
40             }
41             if( flag )
42                 break;
43         }
44     }
45     return 0;
46 }

View Code

今天把窃听风云的3部看完了个人感觉还是比无间道差了点。。窃听风云第一部感觉质量最高点

just follow your heart