459-B, *1300

Problem - 459B - Codeforces

문제

• $n(2 \leq n \leq 2 \cdot 10^{5})$개의 $b(1 \leq b \leq 10^{9})$가 주어진다
• $b_{i},\ b_{j},\ i \neq j$ 차이의 최대값을 구하고 그 값이 나올 수 있는 경우의 수를 구하라

 

풀이

$b_{i}$의 최대값을 $\mathrm{max}$, 최솟값을 $\mathrm{min}$ 이라고 하자

i) $\mathrm{max=min}$
차이의 최대값이 나오는 경우의 수는 $b$의 값에 따라 개수를 세서 구한다.
$$\mathrm{(max\ value\ b\ number)} \times \mathrm{(min\ value\ b\ number)}$$

ii) $\mathrm{max \neq min}$
차이의 최대값이 나오는 경우의 수는
$$\binom{n}{2}$$

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int n;
int maxval = 0;
int minval = 1e9;
map<int, long long> m;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    int b;
    for(int i = 0; i < n; i++){
        cin >> b;
        if(b > maxval) maxval = b;
        if(b < minval) minval = b;
        m[b]++;
    }
 
    if(maxval != minval) cout << maxval - minval << ' ' << m[maxval]*m[minval] << endl;
    else cout << 0 << ' ' << (long long)n*(n-1)/2 << endl;
 
    return 0;
}cs