哎,每次都是能过测试但是最后system test的时候就挂掉了。。。
郁闷啊。。。每次都是这里或者那里要忘掉然后过不了。。。我要什么时候才能变蓝啊!!!!!!
题目是说有N个齿轮,成一圈啮合,就是齿轮连接成一圈,那么肯定两个相邻的齿轮,一个向左转,另一个肯定向右转咯。注意第一个和最后一个是相邻的哦。
然后给一个数组,标志希望的每个齿轮转的方向。比如4个齿轮的时候,给你"LRLR“,依稀是希望第1,3个齿轮向左转,第2,4个齿轮向右转,很明显这个时候4个齿轮希望的方向都能得到满足。
但是给你”RRRR“的话,很明显是不行的。
所以题目让你求:这一圈N个齿轮中,最少需要拿掉多少个齿轮,然后剩下的齿轮都可以照它希望的方向转,注意拿掉一个齿轮,左右的齿轮就断了,而不会再重新接上。
比如有4个齿轮 希望” LRRR“ ,那么可以拿掉第3个齿轮,然后剩下3个都可以照希望方向转。
我的思路是DP,首先把齿轮的头重新定位一下,因为当第0个和最后一个是相同方向的时候,很烦,所以相当于把齿轮转一下,让新的第0个和最后一个方向不同。
如果全都是一样的话,很明显要拿掉一半才能让剩下的齿轮都可以满足,这里没写,然后就挂了。。。
#include<string> #include<algorithm> #include<vector> #include<iostream> using namespace std; class GearsDiv2{ public: int getmin(string dir) { int first=0; int n =dir.length(); for(int i=0;i<n;i++) if( dir[i]!=dir[(i+1)%n]) { first=(i+1)%n; break; } if (first==0) return (n+1)/2; string s1=dir.substr(0,first); string s2=dir.substr(first,n); dir=s2+s1; vector<int> del(50,0); vector<int> stay(50,0); del[0]=1; for(int i=1;i<n;i++) { if (dir[i]==dir[i-1]) { stay[i]=del[i-1]; } else stay[i]=min(stay[i-1],del[i-1]); del[i]=min(stay[i-1],del[i-1])+1; } return min(stay[n-1],del[n-1]); } };