当前位置:编程学习 > C/C++ >>

UVa 565 - Pizza Anyone?


类型: 暴力枚举,搜索

题目:
You are responsible for ordering a large pizza for you and your friends. Each of them has told you what he wants on a pizza and what he does not; of course they all understand that since there is only going to be one pizza, no one is likely to have all their requirements satisfied. Can you order a pizza that will satisfy at least one request from all your friends?

The pizza parlor you are calling offers the following pizza toppings; you can include or omit any of them in a pizza:
Input Code Topping
A Anchovies
B Black Olives
C Canadian Bacon
D Diced Garlic
E Extra Cheese
F Fresh Broccoli
G Green Peppers
H Ham
I Italian Sausage
J Jalapeno Peppers
K Kielbasa
L Lean Ground Beef
M Mushrooms
N Nonfat Feta Cheese
O Onions
P Pepperoni
Your friends provide you with a line of text that describes their pizza preferences. For example, the line
+O-H+P;
reveals that someone will accept a pizza with onion, or without ham, or with pepperoni, and the line
-E-I-D+A+J;
indicates that someone else will accept a pizza that omits extra cheese, or Italian sausage, or diced garlic, or that includes anchovies or jalapenos.

题目大意:
你负责去订购一个大比萨, 但是你的朋友们对于要添加什么或者不添加什么都有不同的要求。 但是你的朋友们也知道不可能满足全部的要求。所以你要选择一个订购方案,让所有人至少满足其中一个要求。 注意,如果某人不想要哪个,那么不添加那个也算是满足了他的一个要求。

分析与总结:
题目只有16种东西选择, 对于每种东西之是选择或者不选泽两种状态。那么用暴力枚举法完全可以做出。
用一个数字,它的各个二进制位表示定或者不定。枚举0 ~ (1<<16)-1即可。
代码:
[cpp] 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
using namespace std; 
char str[100][100]; 
int nIndex; 
 
 
int main(){ 
#ifdef LOCAL 
    freopen("input.txt", "r", stdin); 
#endif 
    while(gets(str[0])){ 
        nIndex = 1; 
        while(gets(str[nIndex]), str[nIndex++][0]!='.') ;; 
 
        int status=0; 
        bool flag=true; 
        int maxNum = (1<<16)-1; 
        while(status <= maxNum){ 
 
            flag = true; 
            for(int i=0; i<nIndex-1; ++i){ 
                bool ok = false; 
                int pos=0; 
                while(pos < strlen(str[i])){ 
                    if(str[i][pos]=='+'){ 
                        if((status >> (str[i][pos+1]-'A')) & 1 ){  
                            ok = true; break; 
                        } 
                    } 
                    else if(str[i][pos]=='-'){ 
                        if( !((status >> (str[i][pos+1]-'A')) & 1)){ 
                            ok = true; 
                            break; 
                        } 
                    } 
                    pos += 2; 
                } 
                if(!ok){flag=false ; break; } 
            } 
            if(flag) break; 
            ++status; 
        } 
        if(!flag) printf("No pizza can satisfy these requests.\n") ; 
        else{ 
            int pos=0; 
            printf("Toppings: "); 
            while(pos <16){ 
                if(status & 1) printf("%c", pos+'A'); 
                ++pos; status >>= 1; 
            } 
            printf("\n"); 
        }  
    } 
    return 0; 


作者:shuangde800
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,