首页 > 代码库 > hdu--1280--与前类似

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                 else37                 {38                     cout << i << " ";39                 }40             }41             if( flag )42                 break;43         }44     }45     return 0;46 }
View Code

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