2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 2)I-Mismatched Socks

2022-04-24 题解

题目大意：给出若干种颜色的袜子和每种颜色袜子的数量，问能分出多少个含有由不同颜色袜子组成的袜子对。

显然，当某种颜色的袜子数目超过袜子总数的一半时，能组成的袜子对数目就是其它颜色的袜子的数目总和（即其它袜子全部和颜色最多的袜子组合）；否则能组成的袜子对数目就是袜子总数的一半（向下取整）。直接证明“否则能组成的袜子对数目就是袜子总数的一半”这个结论比较困难，但考虑这种取法：每次取剩余袜子最多的颜色和剩余袜子次多的颜色，将从它们中各取一只配对。只要满足最开始颜色的袜子数目不超过袜子总数的一半（且袜子总数是偶数），那么总能取完。

代码很简单

#include <bits/stdc++.h>
using namespace std;
long long a[1005];
int main()
{
    int n, i;
    long long sum;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        sum += a[i];
    }
    sort(a + 1, a + 1 + n);
    if (a[n] >= sum - a[n])
        printf("%lld", sum - a[n]);
    else
        printf("%lld", sum >> 1);
    return 0;
}