首页 > 代码库 > codeforces 493C Vasya and Basketball(二分)

codeforces 493C Vasya and Basketball(二分)

传送门:点击打开链接


题目大意:

有2个队打篮球,然后告诉你,A队投了N次蓝,分别的距离,B队投了M篮,分别的距离。

 As we all know, 篮球有个三分线,然后让你找一个三分线出来,使得A队的得分-B队得分最大。差值相同的情况下,找比分最大的。

压线算2分。

解题思路:

假设一个投篮线。在X处 那么很容易 算出每个队的得分情况。(只需要排序 然后二分哪些值是小于等于他的就好了)。

那么就枚举投篮线就好,只需要在N+M个数字之间枚举。然后再增加一个0和INF 2条线。


总结一下吧:

打了广州之后就已经不搞ACM了,所以好久没写代码,代码真的是越写越丑。读题结束就想到思路的题,写了30分钟。


#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
long long a1[201010],a2[201010];

int main()
{
    long long n,m;
    cin >> n;
    for(long long i = 1;i <= n;i++){
        scanf("%I64d",&a1[i]);
    }
    cin >> m;
    for(long long i = 1;i <= m;i++){
        scanf("%I64d",&a2[i]);
    }
    sort(a1+1,a1+1+n);
    sort(a2+1,a2+1+m);
    long long ans1,ans2,temp1,temp2;
    long long x,y;
    x = upper_bound(a1+1,a1+1+n,0)-a1-1;
    y = upper_bound(a2+1,a2+1+m,0)-a2-1;
    ans1 =  3LL*n-x;
    ans2 =  3LL*m-y;
    for(long long i = 1;i <= n;i++){
        x = upper_bound(a1+1,a1+1+n,a1[i])-a1-1;
        y = upper_bound(a2+1,a2+1+m,a1[i])-a2-1;
        temp1 =  3LL*n-x;
        temp2 =  3LL*m-y;
        if(temp1 - temp2 > ans1-ans2){
            ans1 = temp1;
            ans2 = temp2;
        }
        if(temp1 - temp2 == ans1-ans2){
            if(temp1 > ans1){
                ans1 = temp1;
                ans2 = temp2;
            }
        }
    }
    for(long long i = 1;i <= m;i++){
        x = upper_bound(a1+1,a1+1+n,a2[i])-a1-1;
        y = upper_bound(a2+1,a2+1+m,a2[i])-a2-1;
        temp1 =  3LL*n-x;
        temp2 =  3LL*m-y;
        if(temp1 - temp2 > ans1-ans2){
            ans1 = temp1;
            ans2 = temp2;
        }
        if(temp1 - temp2 == ans1-ans2){
            if(temp1 > ans1){
                ans1 = temp1;
                ans2 = temp2;
            }
        }
    }
    x = upper_bound(a1+1,a1+1+n,0x3f3f3f3f)-a1-1;
    y = upper_bound(a2+1,a2+1+m,0x3f3f3f3f)-a2-1;
    temp1 =  3LL*n-x;
    temp2 =  3LL*m-y;
    if(temp1 - temp2 > ans1-ans2){
        ans1 = temp1;
        ans2 = temp2;
    }
    if(temp1 - temp2 == ans1-ans2){
        if(temp1 > ans1){
            ans1 = temp1;
            ans2 = temp2;
        }
    }
    cout<<ans1<<":"<<ans2<<endl;
    return 0;
}


codeforces 493C Vasya and Basketball(二分)