uva 565 - Pizza Anyone?

简介: 点击打开链接 题目意思:   有16种甜品,现在要做一个批萨,有很多人,每个人喜欢的甜品各不相同,要求我们找到一个方案使得至少让每个人都能够满足一个要求,最后输出这个方案。
+关注继续查看

点击打开链接


题目意思:   有16种甜品,现在要做一个批萨,有很多人,每个人喜欢的甜品各不相同,要求我们找到一个方案使得至少让每个人都能够满足一个要求,最后输出这个方案。


解题思路:   我么知道对于每一个toppings只有两种情况取和不取,那么最多有16种,2^16是很小的,那么我们便可以枚举每一个情况,然后去判断是否每个人都能够满足,加入能够满足直接输出即可。注意这一题的输出是多种情况,不一定和样列相同。时间可能会很慢,还有注意数组的大小


代码:

 

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <list>
using namespace std;

const int MAXN = 100;
char G[MAXN][40]; //存储输入的字符串(注意数组的大小)
int P[16]; //存储每一个状态
int m, ans, len, flag;

//处理问题的函数
void solve(int cnt) {
    int i, j;
    int pos = 15;
    memset(P, -1, sizeof (P)); //初始化为-1
    while (pos >= 0) {
        P[pos] = cnt & 1;
        pos--;
        cnt >>= 1;
    }
    //搜索只要每个人都满足即可判断这种情况就是满足的解
    for (i = 0; i < len; i++) {
        flag = 0;
        for (j = 0; G[i][j] != ';'; j++) {
            if (G[i][j] == '+') {
                j++;
                int t = G[i][j] - 65;
                if (P[t])
                    flag = 1;
            }
            if (G[i][j] == '-') {
                j++;
                int t = G[i][j] - 65;
                if (P[t] == 0)
                    flag = 1;
            }
        }
        if (flag == 0)//如果有一个不满足直接退出
            return;
    }
    if (i == len)
        ans = 1;
}

//输出函数
void output() {
    if (ans) {
        printf("Toppings: ");
        for (int i = 0; i < 16; i++) {
            if (P[i])
                printf("%c", i + 65);
        }
        printf("\n");
    } else
        printf("No pizza can satisfy these requests.\n");
}

//主函数
int main() {
    int i;
    while (gets(G[0]) && strcmp(G[0], ".")) {
        i = 1;
        ans = 0;
        while (gets(G[i])) {
            if (strcmp(G[i], ".") == 0)
                break;
            i++;
        }
        len = i;
        m = 65535;//2的16次方减1
        while (m) {//枚举每一种情况
            solve(m);
            if (ans)//找到以后退出不用继续搜索
                break;
            m--;
        }
        output();
    }
    return 0;
}



目录
相关文章
|
4月前
Uva10001 Garden of Eden
Uva10001 Garden of Eden
20 0
|
4月前
uva10152 ShellSort
uva10152 ShellSort
24 0
|
4月前
uva10038 Jolly Jumpers
uva10038 Jolly Jumpers
16 0
|
4月前
uva10112 Myacm Triangles
uva10112 Myacm Triangles
18 0
|
4月前
uva375 Inscribed Circles and Isosceles Triangles
uva375 Inscribed Circles and Isosceles Triangles
18 0
UVa 10082 WERTYU
UVa 10082 WERTYU
83 0
|
机器学习/深度学习
uva 10273 Eat or Not to Eat?
点击打开链接uva 10273 思路: 暴力求解 分析: 1 题目要求没有吃掉的奶牛的个数已经最后一次吃掉奶牛的天数 2 没有其它的方法只能暴力,对于n头牛的n个周期求最小公倍数,然后在2个公倍数之内暴力求解 代码: #inclu...
765 0