[Codeforces493C] Vasya and Basketball

描述 Description

Vasya follows a basketball game and marks the distances from which each team makes a throw. He knows that each successful throw has value of either 2 or 3 points. A throw is worth 2 points if the distance it was made from doesn’t exceed some value of d meters, and a throw is worth 3 points if the distance is larger than d meters, where d is some non-negative integer.

Vasya would like the advantage of the points scored by the first team (the points of the first team minus the points of the second team) to be maximum. For that he can mentally choose the value of d. Help him to do that.

输入格式 InputFormat

The first line contains integer n (1 ≤ n ≤ 2·10⁵) — the number of throws of the first team. Then follow n integer numbers — the distances of throws a_i (1 ≤ a_i ≤ 2·109).

Then follows number m (1 ≤ m ≤ 2·10⁵) — the number of the throws of the second team. Then follow m integer numbers — the distances of throws of b_i (1 ≤ b_i ≤ 2·10⁹).

输出格式 OutputFormat

Print two numbers in the format a:b — the score that is possible considering the problem conditions where the result of subtraction a - b is maximum. If there are several such scores, find the one in which number a is maximum.

样例输入 SampleInput

5
6 7 8 9 10
5
1 2 3 4 5

样例输出 SampleOutput

15:10

Codeforces 493C

代码 Code

可知分数线只有可能为 a 数组或 b 数组中的某个值时才对答案有影响，因此我们排序后枚举每一个数作为分数线来找到最大的差值。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
int a[200005],b[200005],c[400005];
int main()
{
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%d",&m);
    for (i=1;i<=m;i++) scanf("%d",&b[i]);
    sort(a+1,a+n+1);
    sort(b+1,b+m+1);
    for (i=1;i<=n;i++) c[i]=a[i];
    for (i=1;i<=m;i++) c[i+n]=b[i];
    sort(c+1,c+n+m+1);
    l=r=1;
    x=3*n;y=3*m;
    for (i=1;i<=n+m;i++)
    {
        while (l<=n && a[l]<=c[i]) l++;
        while (r<=m && b[r]<=c[i]) r++;
        t=(l-1)*2+(n-l+1)*3;
        k=(r-1)*2+(m-r+1)*3;
        if (t-k>x-y || (t>x && t-k==x-y))
        {
            x=t;
            y=k;
        }
    }
    printf("%d:%d\n",x,y);
    return 0;
}