Codeforces Round #155 (Div. 2)

这场做得很不理想，首先自己的读题速度还是很慢，然后就是调试时暴露的问题，做C题时自己的算法思路没问题，但是可能由于自己不够自信，一直往算法思路上想，结果结果结束后发现，是因为粗心导致两条语句的顺序写错了....

A. Cards with Numbers

题目大意：给2n个数，然后输出n对数，每对数都是相等的.

思路：每个数的范围是1~5000，所以只需要开一个5001的数组记录每个数字出现的次数，如果有一个的次数是奇数，说明是不可能的。然后排序一下，按顺序输出位置即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i, s, n) for(int i=s; i<(n); ++i)
using namespace std;

const int MAXN = 3000005;
int n, m, k;
int cnt[5200];

struct node{
    int x;
    int index;
    friend bool operator<(const node&a,const node&b){
        return a.x < b.x;
    }
}arr[MAXN*2];

bool ok(){
    FOR(i, 1, 5001){
        if(cnt[i]%2==1)return false;
    }
    return true;
}

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    while(~scanf("%d", &n)){
        memset(cnt, 0, sizeof(cnt));
         
        FOR(i,1,2*n+1){
            scanf("%d",&arr[i].x);
            arr[i].index=i;
            ++cnt[arr[i].x];
        }
        if(!ok()){
            puts("-1");
            continue;
        }
        sort(arr+1, arr+2*n+1);
        for(int i=1; i<=2*n; i+=2){
            printf("%d %d\n", arr[i].index, arr[i+1].index);
        }
    }
    return 0;
}

B. Jury Size

题目大意：有n个奥运会要举办，每个奥运会都在一个m月d日开始，而且这个奥运会需要p个人，用t天来准备。准备的时间必须在m月d日的前一天刚好准备好。同一个人一次同时准备一场，求最少需要雇佣多少个人，使得所有奥运会都能恰好准备完。

思路：把日期转换成当年的第几天，例如1月10日，就是2013年的第10天。但是有可能要从2012年就开始准备了。所以可以在原来基础上再加一个数(大于100即可)。然后，由于数据量很少，我们可以暴力，算出每一天需要的人数，取其中人数最多的那一天，就是所需答案。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i, s, n) for(int i=s; i<(n); ++i)
using namespace std;

const int MAXN = 1005;
const int ADD = 400;
int n, m, k;

int nn[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int month[13];
int cnt[1000];

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int m,d,p,t;
    month[0] = 0;
    for(int i=1; i<=12; ++i)
        month[i] = month[i-1]+nn[i];
    while(~scanf("%d", &n)){
        memset(cnt,0,sizeof(cnt));
        REP(i, n){
            scanf("%d%d%d%d",&m,&d,&p,&t);
            int now=month[m-1]+d+ADD;
            int beg = now-t, end = now-1;
            for(int i=beg; i<=end; ++i)
                cnt[i] += p;
        }
        int maxx=-1;
        REP(i, 1000)if(cnt[i]>maxx)maxx=cnt[i];
        printf("%d\n", maxx);
    }
    return 0;
}

C. Anagram

题目大意：有两个字符串s和t，可以改变s中的字符，求最少需要改变s中的几个字符，使得s和t上的每种字符数量都相等，并且s中改变的位置，使得改变后s的字典序最小。

思路：先分别计算出s和t中的每种字符出现的次数，并分别记录在cnt1, cnt2数组中。然后通过观察可以发现，对于字符ch，如果cnt1[ch] < cnt2[ch]，那么肯定是要添加cnt2[ch]-cnt1[ch]个ch字符。那么在让s中的哪些字符是要变换成t中的ch呢？ 对于任意ch，如果cnt1[ch] > cnt2[ch]， 即s中的ch字符数量多了，那么就要把cnt1[ch]-cnt2[ch]个ch字符改变成所需的t中的字符。

再然后，就是改变字符的位置问题，需要按照贪心的思路。把要改变的字符放在按从小到大顺序放入s中要改变的位置（这个位置也从左到右放置），如果当前要放置的是ch，位置是s[i], 会有两种情况：(1) s[i] > ch, 那么只要直接把ch赋给s[i]， 就可以是s的字典序变小。 (2)s[i] < ch, 由于把ch赋给s[i]会使原来的字典序变大，所以要让s[i]这个要改变的尽量往后面放。 例如，s为 AEDEDE， 这三个E中有两个要改变成G，那么就要选择后面两个D变成G。

代码:

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<functional>
#include<set>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i, s, n) for(int i=(s); i<(n); ++i)
using namespace std;

const int MAXN = 1000005;
int n, m, k;
char s[MAXN], t[MAXN];
int cnt1[200], cnt2[200], re[200];

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    while(~scanf("%s%s", s,t)){
        int len=strlen(s);
        memset(cnt1, 0, sizeof(cnt1));
        memset(cnt2, 0, sizeof(cnt2));
        memset(re, 0, sizeof(re));
        REP(i, len){
            ++cnt1[s[i]];
            ++cnt2[t[i]];
        }
        priority_queue<char,vector<char>,greater<char> >Q;
        int cnt=0;
        for(int i='A'; i<='Z'; ++i){
            if(cnt1[i] > cnt2[i]){
                re[i] = cnt1[i]-cnt2[i];
            }
            else if(cnt1[i] < cnt2[i]){
                for(int j=0; j<cnt2[i]-cnt1[i]; ++j){
                    ++cnt;
                    Q.push(char(i));
                }
            }
        }
        int vis[200];
        memset(vis, 0, sizeof(vis));
        REP(i, len)if(re[s[i]] > 0 && !Q.empty()){
            char ch=Q.top();
            ++vis[s[i]];
            if(s[i] > ch || vis[s[i]]+re[s[i]]-1==cnt1[s[i]]){
                --re[s[i]];
                s[i] = ch;
                Q.pop();
            }
        }
        printf("%d\n", cnt);
        puts(s);
    }
    return 0;
}

E. Dormitory

D. Rats

原创http://blog.csdn.net/shuangde800 (转载请标明)