付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0
再用stl 模板的时候 有时候我们只要前n 的排位就可以 而不需要全部的 用sort 就太浪费了
结合之前在hdu 上做的 一道排序题 http://www.cppblog.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 付翔 阅读(1072) 评论(0)  编辑 收藏 引用 所属分类: c++

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2010年5月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜