Google code jam 2008, Round 1A: B.Milkshakes 贪心算法实现

Problem

You own a milkshake shop. There are N different flavors that you can prepare, and each flavor can be prepared "malted" or "unmalted". So, you can make 2N different types of milkshakes.

Each of your customers has a set of milkshake types that they like, and they will be satisfied if you have at least one of those types prepared. At most one of the types a customer likes will be a "malted" flavor.

You want to make N batches of milkshakes, so that:

• There is exactly one batch for each flavor of milkshake, and it is either malted or unmalted.

• For each customer, you make at least one milkshake type that they like.

• The minimum possible number of batches are malted.

Find whether it is possible to satisfy all your customers given these constraints, and if it is, what milkshake types you should make.

If it is possible to satisfy all your customers, there will be only one answer which minimizes the number of malted batches.

Input

• One line containing an integer C, the number of test cases in the input file.

For each test case, there will be:

• One line containing the integer N, the number of milkshake flavors.

• One line containing the integer M, the number of customers.

• M lines, one for each customer, each containing:All of these numbers are separated by single spaces.

• No pair will occur more than once for a single customer.

• Each customer will have at least one flavor that they like (T >= 1).

• Each customer will like at most one malted flavor. (At most one pair for each customer has Y = 1).

• An integer T >= 1, the number of milkshake types the customer likes, followed by

• T pairs of integers "X Y", one for each type the customer likes, where X is the milkshake flavor between 1 and N inclusive, and Y is either 0 to indicate unmalted, or 1 to indicated malted. Note that:

Output

• C lines, one for each test case in the order they occur in the input file, each containing the string "Case #X: " where X is the number of the test case, starting from 1, followed by:

• The string "IMPOSSIBLE", if the customers' preferences cannot be satisfied; OR

• N space-separated integers, one for each flavor from 1 to N, which are 0 if the corresponding flavor should be prepared unmalted, and 1 if it should be malted.

Limits

Small dataset

C = 100
1 <= N <= 10
1 <= M <= 100

Large dataset

C = 5
1 <= N <= 2000
1 <= M <= 2000

The sum of all the T values for the customers in a test case will not exceed 3000.

Sample

 Input Output `2531 1 12 1 0 2 01 5 0121 1 01 1 1` ```Case #1: 1 0 0 0 0Case #2: IMPOSSIBLE ```

In the first case, you must make flavor #1 malted, to satisfy the first customer. Every other flavor can be unmalted. The second customer is satisfied by getting flavor #2 unmalted, and the third customer is satisfied by getting flavor #5 unmalted.

In the second case, there is only one flavor. One of your customers wants it malted and one wants it unmalted. You cannot satisfy them both.

• 每一种口味的奶昔都会有且只有一桶，而且它要么是添加麦乳精的要么是不添加的

• 对每一位顾客，你都应该至少准备一桶他们喜欢的类型。

• 含麦乳精的桶数尽可能的最少。

找出有没有可能在这些约束条件下满足所有的顾客，如果满足，你需要制作那些口味的奶昔。

如果可以满足所有的顾客，那么将会只有一个答案的添加麦乳精的奶昔桶数是最少的。

•  包含一个整数C的一行，表示在输入文件里的测试用例数

对于每一个测试用例，会有：

• 包含一个整数N的一行，奶昔口味数

• 包含一个整数M的一行，顾客数

• M行，每一行对应一个顾客，包含：

• 对于每一位顾客没有一个整数对会出现1次以上

• 每一位顾客至少有一种喜欢的口味（T >= 1)

• 每一位顾客最多喜欢一种添加麦乳精的奶昔口味。（也就是说对于每一位顾客最多有一个整数对的Y = 1）

• 一个整数T >= 1，顾客喜欢的奶昔口味数，紧接着是：

• T个整数对"X Y"，一个是表示顾客喜欢的口味，X取值从1到N（包含），另一个Y为0表示不添加麦乳精，为1表示添加麦乳精。注意

所有的这些数字都用空格分开。

输出

•  C行，一行对应输入文件中出现的一个测试用例，每一行包含一个字符串"Case #X: "，X表示第几个测试用例，从1开始，紧跟着是：

• 字符串"IMPOSSIBLE"，表示如果用户的需求不能被满足 或者

• N个用空格分开的整数，表示从1到N的每一种口味，如果是0表示对应的口味应该不添加麦乳精，如果是1表示应该添加麦乳精。

C = 100

1 <= N <= 10
1 <= M <= 100

C = 5
1 <= N <= 2000
1 <= M <= 2000

在一个测试用例中所有顾客的全部T值的和不会超过3000

输入
2
5
3
1 1 1
2 1 0 2 0
1 5 0
1
2
1 1 0
1 1 1

输出
Case #1: 1 0 0 0 0
Case #2: IMPOSSIBLE

Using the following steps, we can quickly find whether a solution exists, and if so, what the solution is.

1. Start with every flavor unmalted and consider the customers one by one.

2. If there is an unsatisfied customer who only likes unmalted flavors, and all those flavors have been made malted, then no solution is possible.

3. If there is an unsatisfied customer who has one favorite malted flavor, then we must make that flavor malted. We do this, then go back to step 2.

4. If there are no unsatisfied customers, then we already have a valid solution and can leave the remaining flavors unmalted.

```#include <iostream>
#include <map>
#include <vector>
using namespace std;
///////////////////////////SubMain//////////////////////////////////
class CCustomer
{
public:
int types;
map<int, int> malt;
bool satisfied;
bool isLike(int flavor, int malted)
{
map<int,int>::iterator it = malt.find(flavor);
if (it != malt.end())
{
if (it->second == malted)
{
return true;
}
else
{
return false;
}
}

return false;
}

bool isSatisfied(const vector<int>& flavors)
{
for (int i = 0; i < flavors.size(); i++)
{
if (isLike(i + 1, flavors[i]))
{
return true;
}
}
return false;
}

int countMalted()
{
int m = 0;
for (map<int, int>::iterator it = malt.begin(); it != malt.end(); it++)
{
if (it->second == 1)
{
m++;
}
}

return m;
}
};
int main(int argc, char *argv[])
{
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int nCases = 0;
cin >> nCases;
cin.get();
for (int i = 0; i < nCases; i++)
{
cout << "Case #" << i + 1 << ": ";
int flavors = 0;
cin >> flavors;
vector<int> milkshakes;
vector<CCustomer> allCustomers;
int customers = 0;
cin >> customers;
for (int j = 0; j < customers; j++)
{
CCustomer c;
cin >> c.types;
for (int k = 0; k < c.types; k++)
{
int x = 0;
int y = 0;
cin >> x;
cin >> y;
c.malt[x] = y;
c.satisfied = false;
}
allCustomers.push_back(c);
}

for (int j = 0; j < flavors; j++)
{
int n = 0;
milkshakes.push_back(n);
}

for (int j = 0; j < customers; j++)
{
CCustomer c = allCustomers[j];
if (!c.isSatisfied(milkshakes))
{
if (c.countMalted() == 0)
{
// 客户只喜欢unmalted
bool all_malted = true;
for (map<int, int>::iterator it = c.malt.begin(); it != c.malt.end(); it++)
{
if (milkshakes[it->first - 1] != 1)
{
all_malted = false;
break;
}
}
if (all_malted)
{
customers = -1;				 // 用-1表示这个case无解
break;
}
}

if (customers >= 0)
{
for (map<int, int>::iterator it = c.malt.begin(); it != c.malt.end(); it++)
{
if (it->second == 1)
{
milkshakes[it->first - 1] = 1;
j = -1;
break;
}
}
}
}
}

if (customers < 0)
{
cout << "IMPOSSIBLE" << endl;
}
else
{
for (int j = 0; j < flavors; j++)
{
cout << milkshakes[j] << " ";
}
cout << endl;
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
///////////////////////////End Sub//////////////////////////////////```

评论 1

1. #1

islike（）函数里面没有更新milkshake，还有题目上说了每个customer至多有一个malted的爱好

一半的生命与梦想9年前 (2015-08-27)回复