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

POJ 3185 - The Water Bowls

据网上传闻,用高斯消元解?(我就是在学高斯消元的时候看到有拿这个题当练手题的)

但是,看到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