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

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

}

巴特西

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

最新文章

热门文章