题目描述:给你n个数 让你两两求和并且输出前m大的数
N<=3000,a[i]<=5000
分析:一开始我是把全部都存起来排个序,然后超内存了,因为空间复杂度为O(n*n) ,第一次接触到空间复杂度的题 ,后来改为存数据大小了(小于等于10000)
#include<bits/stdc++.h>
#define pb(x) push_back(x)
#define sz(x) size(x)
#define ey(x) empty(x)
#define pp() pop(x)
#define cr(x) clear(x)
#define p(x) push(x)
#define t(x) top(x)
#define f(x) front(x)
#define FOR(i,j,n) for(int i=j;i<n;i++)
#define FOR1(i,j,n,a) for(int i=j;i<n;i++)cin>>a[i]
#define mp(x,y) make_pair(x,y)
#define ms(a,x) memset(a,x,sizeof(a))
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m,flag;
while(cin>>n>>m){
flag=0;
int a[3003];
int vis[10004];
ms(vis,0);
FOR1(i,0,n,a);
FOR(i,0,n)FOR(j,i+1,n) vis[a[i]+a[j]]++;
int cnt=0;
for(int i=10000;i>=0;i--){
if(flag)break;
while(vis[i]!=0){
cout<<i;
vis[i]--;
cnt++;
if(cnt!=m)cout<<' ';
else {cout<<endl;flag=1;break;}
}
}
}
}

京公网安备 11010502036488号