BC 两道其实都是水 没有完整地想好直接就码出事情。wa了一次以后要找bug，找完要把思路理的非常清楚
SPOJ PHT【二分】
#include<bits/stdc++.h>
using namespace std; int main()
{
long long n;
int T,CAS=1;
scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
long long left=0;
long long right=10000000;
while(left<right)
{
long long mid=left+(right-left+1)/(long long)2;
long long temp;
temp=(1LL+mid)*(1LL+mid)-1;
if(n>=temp)
left=mid;
else
right=mid-1;
}
printf("Case %d: ",CAS++);
printf("%lld\n",left);
}
return 0;
}
SPOJ INUM【最小/大值重复】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL; const int N=1e5+10; int n; vector<LL>xs;
map<LL,LL>mp; LL get_min()
{
LL ans;
if(n==xs.size())
{
LL temp=1e18;
for(int i=1;i<xs.size();i++)
{
LL xx=xs[i]-xs[i-1];
if(temp>xx)
{
temp=xx;
ans=1;
}
else if(temp==xx)
ans++;
}
}
else
{
ans=0;
for(int i=0;i<xs.size();i++)
{
if(mp[xs[i]]>1)
ans+=mp[xs[i]]*(mp[xs[i]]-1)/2;
} }
return ans;
} LL get_max()
{
if(xs.size()==1)
{
LL xx=mp[xs[0]];
return xx*(xx-1)/2;
}
else
return mp[xs[0]]*mp[xs[xs.size()-1]];
} int main()
{
while(~scanf("%d",&n))
{
LL x;
xs.clear();
mp.clear(); for(int i=1;i<=n;++i)
{
scanf("%lld",&x);
if(!mp[x])
xs.push_back(x);
mp[x]++;
} if(n==1)
{
printf("0 0\n");
continue;
} sort(xs.begin(),xs.end()); printf("%lld %lld\n",get_min(),get_max()); }
return 0;
}
/*
3
1 2 2
*/