首页 > 代码库 > POJ 3185 - The Water Bowls

POJ 3185 - The Water Bowls

2024-10-19 17:41:02   212人阅读

据网上传闻，用高斯消元解？（我就是在学高斯消元的时候看到有拿这个题当练手题的）

但是，看到discuss上有人说根本不用什么高斯消元和搜索，我一想也是……这题显然用贪心啊……

 

首先前提：翻转问题，1、每个碗只有主动翻转一次和不主动翻转两种情况；2、主动翻转碗的顺序对结果没有影响。

于是我们的思路是，强制按照从左到右这个顺序翻碗碗，

那么，如果有个bowl[i]是1（并且bowl[1]……bowl[i-1]都已经是0），我们要把他变成0，只能翻bowl[i+1]，否则，若是我们翻bowl[i]，就会影响到bowl[i-1]，由于我们强制按照从左到右翻碗，那么这样的情况是不能接受的。

于是，我们就有大体思路，从左到右，枚举每个碗bowl[i]，根据bowl[i-1]的情况看他应不应该主动翻转，

当然，由于bowl[1]比较特殊，因为没有bowl[0]，所以我们可以分情况试一下翻和不翻bowl[1]两种情况，分别记录step，最后输出小的那个即可。

（题目给的测试用例应该都是可以翻到最后，全翻成0的，所以不考虑impossible的情况）

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int tmp[23],bowl[23],step1=0,step2=0;
 5 void flip(int x){for(int i=x-1;i<=x+1;i++) bowl[i]=!bowl[i];}
 6 int main()
 7 {
 8     for(int i=1;i<=20;i++) {scanf("%d",&tmp[i]);bowl[i]=tmp[i];}
 9     
10     for(int i=2;i<=20;i++)
11     {
12         if(bowl[i-1])
13         {
14             flip(i);
15             step1++;
16         }
17     }
18     
19     for(int i=1;i<=20;i++) bowl[i]=tmp[i];
20     flip(1);step2++; 
21     for(int i=2;i<=20;i++)
22     {
23         if(bowl[i-1])
24         {
25             flip(i);
26             step2++;
27         }
28     }
29     
30     printf("%d\n",min(step1,step2));
31 }

总的来说，是一道比较水的问题。

POJ 3185 - The Water Bowls


联系
我们