0%

Codeforces 459B 解题报告

发表于 更新于 分类于 ， ，

题意简述

给定一个数字 \(n(2 \leq n \leq 2 \cdot 10 ^ 5)\) 和 \(n\) 个整数 \(b _ 1,b _ 2.....b _ n(1 \leq b _ i \leq 10 ^ 9)\) 。输出序列中最大的元素和最小的元素的差，以及从序列中选择两个元素，有多少种方案使这两个元素的差最大。

时间限制：1s 空间限制：256MB

题目链接

Codeforces 459B

题解

找到序列中最大的元素与最小的元素并计算个数。如果最大元素不等于最小元素，最大差值为最大元素减去最小元素，方案数为最大元素与最小元素的个数的乘积；如果最大元素等于最小元素，设最大元素个数为 \(n\) ，最大差值为 \(0\) ，方案数为 \(1 + 2 + 3 + ...... + n - 1\) ，即 \(\frac{n \times n - 1}{2}\)。

在统计最大元素和最小元素的过程中，要注意选中的两个元素不能为一个，不能同时更新最大值和最小值。于是优先更新最大值与最大值计数，在更新最大值的过程中如果旧有最大值可用于更新最小值，则用旧有最大值更新最小值，同时更新用旧有最大值计数更新最小值计数，然后更新最大值与最大值计数。判断最大元素与最小元素是否相同只需要检查最小值是否被更新过。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int maxValue = -INF,maxValueCount = 1,minValue = INF,minValueCount = 1;
    for(int i = 0;i < n;i++) {
        int tmpValue;
        cin >> tmpValue;
        if(tmpValue > maxValue) {
            if(maxValue != -INF && maxValue < minValue) {
                minValue = maxValue;
                minValueCount = maxValueCount;
            }
            maxValue = tmpValue;
            maxValueCount = 1;
        }else if(tmpValue == maxValue) {
            maxValueCount++;
        }else if(tmpValue < minValue) {
            minValue = tmpValue;
            minValueCount = 1;
        }else if(tmpValue == minValue) {
            minValueCount++;
        }
    }
    if(minValue == INF) {
        long long result = (1 + maxValueCount - 1) * 1LL * (maxValueCount - 1) / 2;
        cout << 0 << " " << result << endl;
    }else {
        cout << maxValue - minValue << " " << maxValueCount * 1LL * minValueCount << endl;
    }
    return 0;
}