Codeforces 459 B Pashmak and Flowers(水題)
3759 ワード
タイトルリンク:Codeforces 459 B Pashmak and Flowers
シーケンスの差分値が最大の値を見つけ、どのような選択肢が出力されますか.
問題解決の考え方:配列を並べ替えて、最大値から最小値を減算して差の最大値でも、最大値の個数と最小値の個数を統計して、乗算して答えでも.注意すべて同じ場合、C(2 n)であり、総数はintで爆発する.
シーケンスの差分値が最大の値を見つけ、どのような選択肢が出力されますか.
問題解決の考え方:配列を並べ替えて、最大値から最小値を減算して差の最大値でも、最大値の個数と最小値の個数を統計して、乗算して答えでも.注意すべて同じ場合、C(2 n)であり、総数はintで爆発する.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2 * 1e5 + 5;
typedef long long ll;
int n, b[maxn];
int main () {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &b[i]);
sort(b, b + n);
int dis = b[n-1] - b[0];
ll p = 0, q = n-1, ans;
if (dis == 0) {
ans = (ll)n * (n - 1) / 2;
} else {
while (b[p] == b[0] && p < n) p++;
while (b[q] == b[n-1] && q >= 0) q--;
ans = p * (n-1-q);
}
printf("%d %lld
", dis, ans);
return 0;
}