lowsfish

贪心专场？。。

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;
	}
};