再用stl 模板的時候 有時候我們只要前n 的排位就可以 而不需要全部的 用sort 就太浪費了
結合之前在hdu 上做的 一道排序題
http://www.shnenglu.com/397993401/archive/2010/05/24/116261.html 用sort 的代碼
這里則需要46MS 相比先前的600多秒 顯然是快了很多 。。。
#include<iostream>
#include<algorithm>
#include <vector>
#include <functional>
using namespace std;
const int maxn = 3000+10;
int data[maxn];
//int re[maxn*maxn/2];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
int N,M,ans,i;
vector<int > re(maxn*maxn/2);
while(scanf("%d%d",&N,&M)!=EOF)
{
for(i = 0; i < N; i ++)
scanf("%d",&data[i]);
//sort(data,data+N,cmp);
ans = 0;
for( i = 0;i < N;i++)
for(int j = i+1;j<N;j++)
{
re[ans] = data[i]+data[j];
//re.p (data[i]+data[j]);
ans ++;
}
//for( vector<int>::iterator it1 = re.begin(); it1 != re.end() ; it1 ++)
// cout<<*it1<<" ";
//printf("\n");
//partial_sort(re.begin(),re.begin()+M,re.end());//因為申請了axn*maxn/2 空間 所以有很多是0值
/* 這是導致排序后 出現0 值的原因*/
partial_sort(re.begin(),re.begin()+M,re.begin()+ans,cmp);
for( vector<int>::iterator it = re.begin(); it != re.begin()+M&& it != re.end() ; it ++)
if(it ==re.begin()) cout<<*it;
else cout<<" "<<*it;
cout<<endl;// printf("\n");
}
return 0;
}
posted on 2010-05-25 19:00
付翔 閱讀(1092)
評論(0) 編輯 收藏 引用 所屬分類:
c++