题目链接:http://codeforces.com/problemset/problem/459/B
题意:
给出n支花,每支花都有一个漂亮值。挑选最大和最小漂亮值得两支花,问他们的差值为多少,并且有多少种选法(无先后顺序)。
现场做时,想到的是:用multimap记录每个漂亮值出现的次数,并不断更新最大最小值。
这个方法很笨,而且multimap的val值是多余的。
需要注意特殊情况:max==min
代码如下:
#include<iostream>//A - Pashmak and Flowers CodeForces - 459B
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<map> using namespace std;
typedef long long ll; multimap<int,int> m; int main()
{
int n,max = -1,min = 2000000000,a;
ll smax,smin;
m.clear();
scanf("%d",&n);
for(int i = 0; i<n; i++)
{
scanf("%d",&a);
m.insert(pair<int,int>(a,0)); if(a>max) max = a;
if(a<min) min = a;
} smax = m.count(max);
smin = m.count(min); if(max==min)
printf("0 %lld\n",smax*(smax-1)/2);
else
printf("%d %lld\n",max-min, smax*smin); }
后来朋友说排序。恍然大悟,排个序什么都好说了。
代码如下:
#include<iostream>//A - Pashmak and Flowers CodeForces - 459B 排序
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm> using namespace std;
typedef long long ll; ll v[200005]; int main()
{
ll n,max,min,a,j,smax,smin,i; scanf("%lld",&n);
for(i = 0; i<n; i++)
{
scanf("%lld",&v[i]);
}
sort(v,v+n); min = v[0];
smin = 1;
for(i = 1; i<n && v[i]==min; i++)
smin++; max = v[n-1];
smax = 1;
for(i = n-2; i>=0 && v[i]==max; i--)
smax++; if(max==min)
printf("0 %lld\n",smax*(smax-1)/2);
else
printf("%lld %lld\n",max-min, smax*smin);
}