2018 “百度之星”程序设计大赛

rank 264， 三题水过 ~

hdu6380_degree

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 200005;
int in[maxn];
int n,m,k;

int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        memset(in,0,sizeof(in));
        int d = -1;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            in[a]++;in[b]++;
        }
        int ans = -1;
        for(int i=0;i<n;i++)
        {
            ans = max(ans,in[i]+n-m-1+min(k,m-in[i]));
        }
        cout<<ans<<endl;
    }
}

hdu6383_p1m2

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 300005;
int a[maxn];
int n;
bool ok(int x)
{
    int id = lower_bound(a,a+n,x)-a;
    ll ret1 = 0, ret2 = 0;
    for(int i=0;i<id;i++){
        ret1 += (x-a[i]);
    }
    for(int i=id;i<n;i++){
        ret2 += (a[i]-x)/2;
    }
    if(ret1<=ret2){
        return true;
    }
    else{
        return false;
    }
}
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i = 0;i < n;i++)
        {
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        int ans = 0;
        int l = a[0],r = a[n-1];
        while(l <= r)
        {
            int mid = (l+r)>>1;
            if(ok(mid)){
                ans = mid;
                l = mid +1;
            }
            else{
                r = mid - 1;
            }
        }
        cout<<ans<<endl;
    }
}

hdu6385_rect

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n,m,k;
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        int a,b,c;
        ll ans = 0;
        for(int i=0;i<k;i++)
        {
            scanf("%d%d",&a,&b);
            ans += (ll)min(min(a,n-a),min(b,m-b));
        }
        cout<<ans<<endl;
    }
}