Codeforces Round #222 (Div. 2)

题意：每个人选一个1到6之间的数，掷骰子一次，接近谁谁就赢，问第一个人赢和平手和第二个人赢的情况数。

分析：直接模拟。

/****************************************
* File Name: 222a.cpp
* Author: sky0917
* Created Time: 2014年01月10日  8:37:05
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

inline int ab(int x){
    return x>0?x:-x;
}
int main(){
    int a, b;
    int l, m, r;
    while (scanf("%d %d",&a,&b)!=EOF){
        l = m = r = 0;    
        for (int i=1; i<=6; i++){
            if (ab(a-i)<ab(b-i))l++;
            else if(ab(a-i)>ab(b-i))r++;
            else m++;
        }
        printf("%d %d %d
",l,m,r);
    }
    return 0;
}

B. Semifinals

题意：从两个有n个人的半决赛中一共选出n个人参加决赛，你可以指定每个半决赛的前k个人直接入围决赛，剩下人里面再找出成绩最好的n-2*k人入围，问那些人可能进入决赛。

分析：考虑极端情况, k=0 和 k=n/2 两种情况里的可能出现的人。

/****************************************
* File Name: 222b.cpp
* Author: sky0917
* Created Time: 2014年01月11日 20:35:44
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100005;

struct node{
    int ty;
    int va;
    int xu;
}t[maxn*2];

bool cmp(node a, node b){
    return a.va < b.va;
} 

int main(){ int n;

    while (scanf("%d",&n)!=EOF){
        int ta = -1, tb = -1;
        for (int i=0; i<n; i++){
            scanf("%d %d",&t[i].va,&t[i+n].va);
            t[i].ty = 0; t[i+n].ty = 1;        
            t[i].xu = t[i+n].xu = i;
        }    

        sort(t, t+n*2, cmp);  
        for (int i=n-1; i>=0; i--){
            if (ta == -1 && t[i].ty == 0){
                ta = t[i].xu;
            }
            if (tb == -1 && t[i].ty == 1){
                tb = t[i].xu;
            }
            if (ta != -1 && tb != -1){
                break;
            }
        }
        ta = max(ta, n/2-1);
        tb = max(tb, n/2-1);        
        for (int i=0; i<=ta; i++){
            putchar('1');
        }
        for (int i=ta+1; i<n; i++){
            putchar('0');
        }
        puts("");
        for (int i=0; i<=tb; i++){
            putchar('1');
        }
        for (int i=tb+1; i<n; i++){
            putchar('0');
        }
        puts("");
    }
    return 0;
}

C. Maze

题意：有个迷宫，里面有两种地形，. 和 #, #是墙头，.一开始是连通的，现在把迷宫中找出k个 . 变成#，使得 . 还是连通的。

分析：算出剩下的点 . 的个数n，从一个点 . dfs出n个可到达的点.，剩下的变成墙头即可。

/****************************************
* File Name: 222c.cpp
* Author: sky0917
* Created Time: 2014年01月11日 21:02:21
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 505;

char g[maxn][maxn];
int n, m, k;
int tot, sum;
int f[8] = {-1, 1, 0, 0, 0, 0, -1, 1};
inline bool ok(int x, int y){
    return x>=0 && x<n && y>=0 && y<m && g[x][y] == 'X' && sum > 0;
}
void dfs(int x, int y){

    for (int i=0; i<4; i++){
        int xx = x + f[i];
        int yy = y + f[i+4];
        if (ok(xx, yy)){
            sum--;
            g[xx][yy] = '.';
            dfs(xx, yy);
        }
    }   
}
int main(){
    int sx, sy;
    while (scanf("%d %d %d",&n,&m,&k)!=EOF){
        tot = 0;    
        for (int i=0; i<n; i++){
            scanf("%s",g[i]);
            for (int j=0; j<m; j++){
                if (g[i][j]  == '#')
                    tot++;
                else
                    g[i][j] = 'X';
            }   
        }
        sum = n * m - tot - k;  
        for (int i=0; i<n; i++){
            for (int j=0; j<m; j++){
                if (g[i][j] == 'X' && sum>0){
                    sum--;
                    g[i][j] = '.';
                    dfs(i, j);
                    goto loop;              
                }
            }
        }
loop:   for (int i=0; i<n; i++){
            for (int j=0;j<m; j++){
                putchar(g[i][j]);
            }
            puts("");
        }   
    }   
    return 0;
}

D. Preparing for the Contest

题意：有m个bug要修好，现在有n个学生，每个bug有个要求值ai，每个学生有个能力值bi，当bi>=ai时学生能修这个bug，并且花掉他一天的时间，每个学生雇佣要花ci元，一次雇佣，

终身受用，一共有 s 的资金，问是否能修好所有bug，并且要求资金够用，花的时间最少。

分析：首先二分时间即天数，关键是如何判断这个天数 ti 下是否能完成任务。

先对ai从大到小排序，再对学生按照 bi 从大到小排序，考虑修能力值为 bi 的bug时，所有ai>=bi的学生都可以维修，我们只要从这里找到ci最小的那个即可，而且一旦修了，那么让

bi 后面的ti-1个也被修了，这里可以维护一个优先队列，优先级按照ci从小到大，按 bi 从大到小依次加入满足条件的学生，每次队首的元素就是满足条件的元素。

/****************************************
* File Name: 222d.cpp
* Author: sky0917
* Created Time: 2014年01月12日 21:09:58
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100005;

int n, m, s;
struct node{
    int bi;
    int ci;
    int xu;
    bool operator < (const node& tq)const{
        return ci > tq.ci; 
    }
}q[maxn];


struct bug{
    int ai;
    int xu;
}a[maxn];

bool cmp(node ca, node cb){
    return ca.bi > cb.bi;
}
bool cmp2(bug ca, bug cb){
    return ca.ai < cb.ai;
}
int ans[maxn];
int tp;
bool ok(int ti){
    
    priority_queue<node>que;
    int sum = 0;
    int j = 0;
    int k;
    tp = 0;

    for (int i=m-1; i>=0; i--){
        while (j < n && q[j].bi >= a[i].ai){
            que.push(q[j++]);
        }    
        if (!que.empty()){
            node tt = que.top();
            que.pop();
            sum += tt.ci;
            k = i;
            i = i - ti + 1;         
            for (;k>=i && k>=0; k--){
                ans[a[k].xu] = tt.xu+1;
            }
            if (sum > s) return false;
        }
        else return false;
    }

    return true;
}
void solve(){

    sort(a, a+m, cmp2);
    sort(q, q+n, cmp);
     
    int l = 1, r = m, mid;
    int res = 0;
    while (l <= r){
        mid = (l+r)>>1;
        if (ok(mid)){
            res = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    if (res){
        ok(res);
        printf("YES
");
        for (int i=0; i<m; i++){
            printf("%d%c",ans[i],i==m-1?'
':' ');
        }    
    }    
    else {
        printf("NO
");
    }
}

int main(){

    while (scanf("%d %d %d",&n,&m,&s)!=EOF){
        for (int i=0; i<m; i++){
            scanf("%d",&a[i].ai);
            a[i].xu = i;
        }
        for (int i=0; i<n; i++){
            scanf("%d",&q[i].bi);
        }
        for (int i=0; i<n; i++){
            scanf("%d",&q[i].ci);
            q[i].xu = i;
        }
        solve();    
    }    
    return 0;
}