学步园

题意：有一个人欠三个人分别p o s（1<=p o s<=10^5）块钱，现在这个人手里有n（1<=n<=10^5）块crystal，但是每块crystal在不同人看来是不一样的

          价值（1块或者2块），现在问是否存在一种分配方案使得能还清3个人的钱。

题解：首先给不同的crystal排优先级，然后枚举满足三个人的优先级后贪心。

Sure原创，转载请注明出处

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#define MAX(a , b) ((a) > (b) ? (a) : (b))
using namespace std;
const int pp[9] = {8,1,2,4,3,5,6,7};
const int maxn = 100002;
struct node
{
    int val[3];
    int id,pro;
    bool operator < (const node &other) const
    {
        return pro < other.pro;
    }
}crystal[maxn];
int belong[maxn];
int a[3],rank[3],n,p,o,s;

void read()
{
    char str[5];
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%s",str);
        int c = 0;
        crystal[i].id = i;
        for(int j=0;j<3;j++)
        {
            c <<= 1;
            if(str[j] == 'B')
            {
                crystal[i].val[j] = 2;
                c |= 1;
            }
            else crystal[i].val[j] = 1;
        }
        crystal[i].pro = pp[c];
    }
    sort(crystal , crystal + n);
    return;
}

void out()
{
    for(int i=0;i<n;i++)
    {
        if(belong[i] == 0) printf("P");
        else if(belong[i] == 1) printf("O");
        else printf("S");
    }
    puts("");
    return;
}

bool check(int xx,int yy,int zz)
{
    a[0] = p;
    a[1] = o;
    a[2] = s;
    rank[0] = xx;
    rank[1] = yy;
    rank[2] = zz;
    for(int i=0;i<n;i++)
    {
        int j;
        for(j=0;j<3;j++)
        {
            if(crystal[i].val[rank[j]] == 2 && a[rank[j]] > 1)
            {
                a[rank[j]] -= 2;
                belong[crystal[i].id] = rank[j];
                break;
            }
        }
        if(j == 3)
        {
            for(j=0;j<3;j++)
            {
                if(a[rank[j]] > 0)
                {
                    a[rank[j]]--;
                    belong[crystal[i].id] = rank[j];
                    break;
                }
            }
            if(j == 3) belong[crystal[i].id] = 0;
        }
    }
    return (a[0] <= 0 && a[1] <= 0 && a[2] <= 0);
}

void solve()
{
    if(check(0,1,2)) {out();return;}
    if(check(0,2,1)) {out();return;}
    if(check(1,0,2)) {out();return;}
    if(check(1,2,0)) {out();return;}
    if(check(2,0,1)) {out();return;}
    if(check(2,1,0)) {out();return;}
    puts("no solution");
    return;
}

int main()
{
    while(~scanf("%d %d %d",&p,&o,&s))
    {
        read();
        solve();
    }
    return 0;
}