Codeforces Round #261 (Div. 2) B. Pashmak and Flowers 水题

时间:2021-11-17 23:30:27

题目链接: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);
}