uva 1392 - DNA Regions(二分）

题目链接：uva 1392 - DNA Regions

题目大意：给n和p，以及两个DNA序列，要求找出其中突变率不超过p%的最长子串的长度。

解题思路：s[i]表示前i个有s[i]个突变，这样的话就有s[j] - s[i]/(j - i) ≤ p * 100,即有s[j] *100 - p * j ≤ s[i] * 100 - p * i为区间[i,j]是否符合突变率小于p%；也就是说对于每个位置，找到一个最小的x，满足s[x] * 100 - p * x ≥ s[i] * 100 - p * i,长度i-x即为i往前的最优解。所以只要维护一个递减序列，然后二分即可。

#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>

using namespace std;
const int N = 150005;
const int INF = 0x3f3f3f3f;

struct state {
	int sum, id, key;
}s[N], c[N];

int n, p, ans, cnt;
char a[N], b[N];

int find (int key) {
	int l = 0, r = cnt - 1;
	while (l < r) {
		int mid = (l + r) / 2;
		if (c[mid].key <= key) r = mid;
		else l = mid+1;
	}
	return c[l].id;
}

bool solve () {
	ans = 0;

	cnt = 1;
	s[0].sum = s[0].id = 0; s[0].key = 0;
	c[0] = s[0];

	for (int i = 1; i <= n; i++) {
		s[i].sum = s[i-1].sum + (a[i-1] != b[i-1]);
		s[i].id = i; s[i].key = i * p - 100 * s[i].sum;

		if (s[i].key < c[cnt-1].key) {
			c[cnt++] = s[i];
		} else {
			int t = find(s[i].key);
			ans = max(ans, s[i].id - t);
		}
	}
	if (ans) return true;
	return false;
}

int main () {
	while (scanf("%d%d", &n, &p) == 2 && n + p) {
		scanf("%s%s", a, b);
		if (solve()) printf("%d\n", ans);
		else printf("No solution.\n");
	}
	return 0;
}