Sgu/299 2015年2月17日 (二) 18:13云璟月（讨论 | 贡献）的版本 (差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
Triangle	★☆☆☆☆	答案正确	100	2015-2-17 18:14:07	无

（AC 1046）

题意

给出一堆数，求出其中是否能组成三角形的（高精度）。

题解

众所周知组成三角形只要两边之和大于第三边

a+b>c
a+c>b
b+c>a

假设a≤b≤c的情形下，实际上只要满足第一个条件。

而对于排序好的一堆数，要使得存在满足第一个条件的a,b,c，那么a,b要尽量大，c要尽量小，也就是排序好数列中，连续三个数比不连续的更优。因此只要O(n)地判断一遍连续三个数是否存在满足的一组数。

用上高精度类（CodeVS/3115），排序一下，按上述方式判断即可。

代码

299.cpp代码已折叠 展开折叠内容

#include<iostream> #include<iomanip> #include<algorithm> #include<vector> using namespace std; class unsigned_huge_int { public: const size_t size() const { return u.size(); } friend const bool operator <(const unsigned_huge_int &a,const unsigned_huge_int &b) { if(a.size()==b.size()) { for(int i=a.size()-1;i>=0;--i){ if(a.u[i]!=b.u[i]) return a.u[i]<b.u[i]; } return 0; } return a.size()<b.size(); } friend const bool operator ==(const unsigned_huge_int &a,const unsigned_huge_int &b) { if(a.size()==b.size()) { for(int i=a.size()-1;i>=0;--i){ if(a.u[i]!=b.u[i]) return 0; } return 1; } return 0; } friend const bool operator <=(const unsigned_huge_int &a,const unsigned_huge_int &b) { return a<b || a==b; } friend const bool operator >(const unsigned_huge_int &a,const unsigned_huge_int &b) { return !(a<=b); } friend const bool operator >=(const unsigned_huge_int &a,const unsigned_huge_int &b) { return !(a<b); } friend const bool operator !=(const unsigned_huge_int &a,const unsigned_huge_int &b) { return a==b; } unsigned_huge_int() { u.clear(); u.push_back(0); } unsigned_huge_int(const unsigned int &number) { u.clear(); u.push_back(number); refresh(); } unsigned_huge_int(const string&original) { u.clear(); for(int i=original.size()-1,j=0,p=1;i>=0;--i) { j+=(original[i]-'0')*p; p*=10; if((!i) || p==10000) { u.push_back(j); j=0; p=1; } } } friend istream& operator >> (istream& os,unsigned_huge_int &ob) { string original; os>>original; ob=original; return os; } friend ostream& operator << (ostream& os,const unsigned_huge_int &ob) { os<<setw(0)<<setfill('0')<<ob.u[ob.size()-1]; for(int i=ob.size()-2;i>=0;--i) os<<setw(4)<<setfill('0')<<ob.u[i]; return os; } friend const unsigned_huge_int operator +(const unsigned_huge_int &a,const unsigned_huge_int &b) { unsigned_huge_int r; r.u.resize(max(a.size(),b.size())); for(int i=0;i<r.size();++i) { if(i<a.size()) r.u[i]+=a.u[i]; if(i<b.size()) r.u[i]+=b.u[i]; } r.refresh(); return r; } friend const unsigned_huge_int operator *(const unsigned_huge_int &a,const unsigned_huge_int &b) { unsigned_huge_int r; r.u.resize(a.size()+b.size()); for(int i=0;i<a.size();++i) { for(int j=0;j<b.size();++j) { r.u[i+j]+=a.u[i]*b.u[j]; } } r.refresh(); return r; } friend const unsigned_huge_int operator -(const unsigned_huge_int &a,const unsigned_huge_int &b) { unsigned_huge_int r; const unsigned_huge_int *p1=&a,*p2=&b; if(*p1<*p2) swap(p1,p2); r.u.resize(p1->size()); for(int i=0;i<r.size();++i) if(i<p2->size()) r.u[i]+=p1->u[i]-p2->u[i]; else r.u[i]+=p1->u[i]; r.refresh(); return r; } private: vector<int> u; void refresh() { for(int i=0;i<size();++i) { if(u[i]>=10000) { if(i==size()-1) u.push_back(u[i]/10000); else u[i+1]+=u[i]/10000; u[i]%=10000; } while(u[i]<0) { u[i]+=10000; u[i+1]-=1; } } for(int i=size()-1;i!=0;--i) { if(u[i]==0&&size()!=1) { u.pop_back(); }else{ return; } } } } a[2000]={}; int main() { int n; cin>>n; for(int i=1;i<=n;++i) { cin>>a[i]; } sort(a+1,a+n+1); for(int i=1;i+2<=n;++i) { if(a[i]+a[i+1]>a[i+2]) { cout<<a[i]<<" "<<a[i+1]<<" "<<a[i+2]; return 0; } } cout<<"0 0 0"<<endl; return 0; }