Topcoder 11_21

第一次做topcoder，状态不是很好，一个向量容器的排序都让我想了好久，感觉到头文件定义的强大，但是我的头文件明显是不完善的，我只写了常用的几个。

适当的头文件定义可以加快变成的速度：

头文件定义（有待完善）：

#include <cassert>
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <cstdlib>
#include <ctime>
#include <iterator>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <algorithm>

#pragma comment(linker,"/STACK:60777216")

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define SORT(c) sort((c).begin(),(c).end())
#define REV(c) reverse((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a); i < (b);i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define pb push_back

int max(int x,int y) {return x>y?x:y;}
int min(int x,int y) {return x>y?y:x;}
int f_abs(int x) {return (x)>(0)?(x):(-x);}

topcoder div2 500

size有M，L两种，提取出来单独比较(一道题目气球的大小一定要一样)，结果maxAccepted中元素最多为15个，枚举每个题size的状态,复杂度O(2^N*N),比较取出最小的。

class ICPCBalloons{
    public:
    int solve(VI a,VI b) {
        int suma=0,sumb=0;
        FOR(i,0,a.size())suma+=a[i];
        FOR(i,0,b.size())sumb+=b[i];
        if(suma>sumb) return -1;
        else {
            int sum=0;
            SORT(a);  SORT(b);
            REV(a), REV(b);
            for(int i=0,j=0;i<a.size();i++) {
                if(j<b.size()) sum+=max(a[i]-b[j],0),j++;
                else sum+=a[i];
            }
            return sum;
        }
    }
    int minRepaintings(vector <int> bc, string bs, vector <int> mac){
        VI la,ma;
        la.clear(); ma.clear();
        FOR(i,0,bs.size()) {
            if(bs[i]=='M') ma.pb(bc[i]);
            else la.pb(bc[i]);
        }
        int ans=-1,len=mac.size();
        VI L,M;
        FOR(mask,0,1<<len) {
            L.clear(); M.clear();
             FOR(j,0,len) {
                 if(mask&(1<<j)) M.pb(mac[j]);
                 else L.pb(mac[j]);
             }
             int ansl=solve(M,ma),ansm=solve(L,la);
             if(ansl==-1 || ansm==-1) continue;
             ansl+=ansm;
             if(ans==-1||ans>ansl) ans=ansl;
        }
        return ans;
    } 
};