搜狐笔试

全A了，提供下项链O(N)解法，代码可以更精简点，过了就没管了 #include <iostream> #include <string> #include <deque> using namespace std; int cut(const string &neck) { int i = 0; int j = 0; int mini = neck.length() / 2; int flag[5] = {0}; int count_f = 5; deque<char> deq; deque<int> pos; while(i < neck.length() / 2 && j < neck.length()) { if(neck[j] <= 'E') { if(deq.empty()) { i = j; deq.push_back(neck[j]); pos.push_back(j); flag[neck[j] - 'A'] = 1; count_f--; } else if(deq.front() == neck[j]) { deq.push_back(neck[j]); pos.push_back(j); flag[neck[j] - 'A']++; char head = deq.front(); while(flag[head - 'A'] > 1) { deq.pop_front(); pos.pop_front(); flag[head - 'A']--; head = deq.front(); i = pos.front(); }; } else { deq.push_back(neck[j]); pos.push_back(j); if(flag[neck[j] - 'A'] == 0) { count_f--; } flag[neck[j] - 'A']++; } if(count_f == 0) { if(mini > j - i + 1) { mini = j - i + 1; } } } j++; } return neck.length() / 2 - mini; } int main() { string neck; while(cin>>neck) { cout<<cut(neck + neck)<<endl; } return 0; }

2.6赛马网跟我有仇似的

1 0.4 0.4

项链60%TLE。。2.6

同求思路

Ac 0.8 AC 急着上厕所，不折腾了

AC 2.4 1 0.8不tle了，但是还有0.2不知为何 0.6 考虑了回跳，但依然0.6不知为何