贪心专场?。。
250:给出一个字符串\(s\)和一个整数\(L\),每次可以选择一个下标\(i(0\le i\le length(s)-L)\)进行一个操作:保持\(0\sim i-1\)这些字符不变,\(i\sim (i+L-1)\)这些字符按照字典序重新排序,\((i+L)\sim n\)这些字符全部删除。问最后能剩下的字典序最小的序列是什么。。
直觉这么写是对的。。然后就这么写了。。
class EllysSortingTrimmer { public: string getMin(string S, int L) { for(int i = (int)S.length() - L; i >= 0; --i) sort(S.begin() + i, S.begin() + i + L); return S.substr(0, L); } };
500:给出一个字符串\(s\),需要把字符串中的字符重新排列,要求一个字符移动的距离不能超过\(maxDistance\),求字典序最小的序列。
从\(0\)到\(n-1\)扫。。扫到位置\(i\)的时候,如果原串中位置为\(i-maxDistance\)的那个字符还没放,就把它放在这里,否则在允许范围内选一个最小的字符放在这里
bool vis[55] = {}; class EllysScrabble { public: string getMin(string s, int L) { memset(vis, 0, sizeof vis); int len = s.length(); string ns = ""; for(int i = 0; i < len; ++i) { if(i >= L && !vis[i - L]) ns += s[i - L], vis[i - L] = true; else { char c; int t; c = 'Z' + 1; for(int j = max(0, i - L); j < min(len, i + L + 1); ++j) { if(s[j] < c && !vis[j]) c = s[j], t = j; } vis[t] = true; ns += c; } } return ns; } };
1000:有\(n\)个灯和\(n\)个开关,开关\(i\)一定控制灯\(i\),也可能控制灯\(i-1\),也可能控制\(i+1\),也可能都控制,然而你并不知道它会控制哪些(如果控制的话按下开关相应的灯状态会改变)。问在最坏情况下,至少有多少灯会一直亮着(即所有可能的状态中,亮灯最少的那个状态亮灯的个数)
通过分析发现,只有’YN’ 或者’YN’或者’YYY’这三种情况可能会导致至少有一盏灯会在这2(3)盏灯中亮着。。数一下有多少这种情况就行了。
class EllysLamps { public: int getMin(string lamps) { int i = 0, ans = 0, n = lamps.length(); while(i + 1 < n) { if ((lamps[i] == 'Y' && lamps[i + 1] == 'N') || (lamps[i] == 'N' && lamps[i + 1] == 'Y')) { ans++; i += 2; continue; } if (i + 2 < n && lamps[i] == 'Y' && lamps[i + 1] == 'Y' && lamps[i + 2] == 'Y') { ans++; i += 3; continue; } ++i; } return ans; } };