| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
|---|---|---|---|---|---|
| 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;
}
|
CloudLunar