题意:给你一系列的棍子,让你拼接成一个矩形,矩形的两条边是A,B,让A/B+B/A最小。多组满足,输出一组即可。
分析:开始我看成了多组满足,输出所有的情况
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<vector>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 3000010
typedef long long ll;
//head
int T,A[maxn],B[maxn],ha[maxn],vis[maxn],n,q;
double Min;
int main(){scanf("%d",&T);while(T--){q=0;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&A[i]);ha[A[i]]++;if(ha[A[i]]==4){B[q++]=A[i];}if(ha[A[i]]==2){B[q++]=A[i];}}for(int i=0;i<n;i++) ha[A[i]]=0;Min=inf;sort(B,B+q);for(int i=0;i<q-1;i++){double tmp;tmp=1.0*B[i+1]/B[i]+1.0*B[i]/B[i+1];Min=min(tmp,Min);}for(int i=0;i<q-1;i++){if(1.0*B[i+1]/B[i]+1.0*B[i]/B[i+1]==Min){printf("%d %d %d %d\n",B[i],B[i],B[i+1],B[i+1]);break;}}}return 0;
}
T了的代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<vector>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 3000010
typedef long long ll;
//head
int T,A[maxn],ha[maxn],vis[maxn],n;
vector<int> ve;
set<int> ss;
int main(){cin>>T;while(T--){memset(ha,0,sizeof(ha));memset(vis,0,sizeof(vis));int flag=false;ve.clear();ss.clear();cin>>n;for(int i=0;i<n;i++){cin>>A[i];ha[A[i]]++;}sort(A,A+n);for(int i=0;i<n;i++){if(ha[A[i]]>=4){flag=true;if(!vis[A[i]]){for(int p=0;p<4;p++) cout<<A[i]<<" ";}cout<<endl;vis[A[i]]=true; }}if(flag) continue;else{int Min=inf;for(int i=0;i<n;i++){if(ha[A[i]]>=2){ss.insert(A[i]);}}set<int>::iterator ite;for(ite=ss.begin();ite!=ss.end();++ite){ve.push_back(*ite);}for(int i=0;i<ve.size()-1;i++){int tmp=ve[i+1]-ve[i];if(tmp<Min){Min=tmp;}}for(int i=0;i<ve.size();i++){if(ve[i+1]-ve[i]==Min){cout<<ve[i]<<" "<<ve[i]<<" "<<ve[i+1]<<" "<<ve[i+1]<<endl;}}}}