挑战程序设计竞赛-day8

优先队列

POJ 2010 Moo University - Financial Aid

思路：

先将奶牛的CSAT按照从大到小（或者从下到大也可以）的顺序排列，然后

• 从前往后求解，若选择当前位置，则判断左边选择N/2个所需要花费的最小金额（rightMin）
• 从后往前求解，若选择当前位置，则判断右边选择N/2个所需要花费的最小金额（leftMin）

最后从前往后遍历，如果rightMin[i] + leftMin[i] - cows[i].second小于所需要的金额的时候，则cows[i].first就是所求答案。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <climits>
using namespace std;
typedef pair<int, int> P;
const int MAXC = 100010;
const int MAXN = 20005;
int N, C, F;
P cows[MAXC];
priority_queue<int, vector<int>, less<int> >que;
priority_queue<int, vector<int>, less<int> >que2;
int rightMin[MAXC];
int leftMin[MAXC];

void solve() {
    int ans = 0;
    memset(rightMin, 0, sizeof(rightMin));
    memset(leftMin, 0, sizeof(leftMin));
    int num = N >> 1;
    int totalSum = 0;
    for(int i = 0;i < C; i++) {
        if(ans <= num) {
            que.push(cows[i].second);
            ans++;
            totalSum += cows[i].second;
            rightMin[i] = totalSum;
            continue;
        }
        rightMin[i] = totalSum - que.top() + cows[i].second;
        if(cows[i].second < que.top()) {
            totalSum -= que.top();
            que.pop();
            que.push(cows[i].second);
            totalSum += cows[i].second;
        }
    }
    totalSum = 0;
    ans = 0;
    for(int i = C - 1; i >= 0; i--) {
        if(ans <= num) {
            que2.push(cows[i].second);
            ans++;
            totalSum += cows[i].second;
            leftMin[i] = totalSum;
            continue;
        }
        leftMin[i] = totalSum - que2.top() + cows[i].second;
        if(cows[i].second < que2.top()) {
            totalSum -= que2.top();
            que2.pop();
            que2.push(cows[i].second);
            totalSum += cows[i].second;
        }
    }
    int CSAT = 0;
    for(int i = num; i < C - num; i++) {
        if(rightMin[i] + leftMin[i] - cows[i].second <= F) {
            CSAT = cows[i].first;
            printf("%d\n", CSAT);
            return ;
        }
    }
    printf("-1\n");
}

int main(){
    while(scanf("%d%d%d", &N, &C, &F) != EOF) {
        for(int i = 0; i < C; i++) {
            scanf("%d%d", &cows[i].first, &cows[i].second);
        }
        sort(cows, cows + C, greater<P>());
        solve();
    }
}

并查集

// 路径压缩的并查集
int find(int i) {
    return f[i] == i ? i : f[i] = find(d[i]);
}

// 初始化
void Init() {
    for(int i = 0; i <= n; i++) {
        par[i] = i;
    }
}

// 查询x的根节点并压缩路径
int Find(int x) {
    return par[x] == x ? x : par[x] = Find(par[x]);
}

// 合并x和y所在的集合
void Union(int x, int y) {
    par[Find(x)] = Find(y);
}

并查集

POJ 2236 Wireless Work

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN = 1010;
int dx[MAXN], dy[MAXN];
int par[MAXN];          // par[x]表示x的父节点
int repair[MAXN] = {0};
int n;

// 初始化
void Init() {
    for(int i = 0; i <= n; i++) {
        par[i] = i;
    }
}

// 查询x的根节点并压缩路径
int Find(int x) {
    return par[x] == x ? x : par[x] = Find(par[x]);
}

// 合并x和y所在的集合
void Union(int x, int y) {
    par[Find(x)] = Find(y);
}

double dis(int a, int b) {
    return sqrt(double(dx[a] - dx[b]) * (dx[a] - dx[b]) + (dy[a] - dy[b]) * (dy[a] - dy[b]));
}

int main() {
    int d, i;
    scanf("%d%d", &n, &d);
    Init();
    for(int i = 0; i < n ;i++) {
        scanf("%d%d", &dx[i], &dy[i]);
    }
    char cmd[2];
    int p, q, len = 0;
    while(scanf("%s", cmd) != EOF) {
        switch (cmd[0])
        {
        case 'O':
            scanf("%d", &p);
            p--;
            repair[len++] = p;
            for(int i = 0; i < len - 1; i++) {
                if(repair[i] != p && dis(repair[i], p) <= double(d)) {
                    Union(repair[i], p);
                }
            }
            break;
        
        case 'S':
            scanf("%d%d", &p, &q);
            p--, q--;
            if(Find(p) == Find(q)) {
                printf("SUCCESS\n");
            } else {
                printf("FAIL\n");
            }
        default:
            break;
        }
    }
    return 0;
}

POJ 1703 Find them, Catch them

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

using namespace std;

const int maxn = 100000+5;

int fa[2*maxn],height[maxn*2];//height数组用来控制并查的方向
int T,N,M,a,b;
char c;

void init()//初始化
{
    for(int i=1; i<=2*N; i++)
    {
        fa[i]=i;
        height[i]=0;
    }
}

int find_(int x)//并查集
{
    return x==fa[x]? x : fa[x]=find_(fa[x]);
}

void unit (int u, int v)
{
    int x,y;
    x=find_(u);
    y=find_(v);
    if(x==y)
    return;
    if(height[y]>height[x])
        fa[x]=y;
    else
    {
        fa[y]=x;
        if(height[x]==height[y])
            height[x]++;
    }
}

bool same(int u, int v)
{
    return find_(u)==find_(v);
}

int main()
{
    scanf("%d",&T);

    while(T--)
    {
        scanf("%d %d",&N,&M);
        init();
        for(int i=0; i<M; i++)
        {
            getchar();
            scanf("%c %d %d",&c,&a,&b);
            if(c=='D')
            {
                unit(a,b+N);// b和b+N不在同一个帮派，则把a和b+N看作一个帮派的，合并得到一起
                unit(a+N,b);// 同理由上可得
            }
            else
            {
                if(same(a,b))
                    printf("In the same gang.\n");
                else if(same(a,b+N))
                    printf("In different gangs.\n");
                else
                    printf("Not sure yet.\n");
            }

        }
    }
    return 0;
}