2013-03-15 21:40:34Morris
[ZJ][最大平均值問題] a639. DNA Density
內容 ： | 正體中文 (zh_TW) | ?????? ()
生物的DNA係由 A, T, C, G 四個字元所構成的序列。因為DNA的序列太長了，我們希望找出比較重要的區段，以方便研究。
生物學家對於某些含有高密度C或G的區段，特別有興趣。因此，請你撰寫程式，尋找具有最高密度C或G的區段。
假設DNA序列的最大長度為120個字元，由大、小寫英文字母ATCG組成。生物學家有興趣的DNA區段，其最小長度為L，5 ≤ L ≤ 40，該區段具有C或G的個數為w，則CG密度為 w/L。
輸入說明
：
有多筆測試資料，每筆測試資料一行，包含一個整數 L 及 DNA 序列，以空白隔開。
輸出說明
：
每筆測式資料，請以一行輸出其最大CG密度，並精確至小數以下第二位。
範例輸入 ：
5 agGCTGCAatGACAGTTGGG 20 AaggctatacagtactaatCtTtTgcatggc
範例輸出 ：
0.83 0.41
提示
：
輸入範例說明：
一、以第一筆測資為例
L=5，表示計算CG密度的最小長度為 5 ，但最大CG密度可能出現在 L = 6, 7, 8, ...。
(1)DNA區段長度為 5，則 gGCTG、GCTGC 的CG密度皆為4/5=0.80。
(2)DNA區段長度為 6，則 gGCTGC 的CG密度為5/6=0.83。
(3)DNA區段長度 7 以上，CG密度皆小於0.83，所以最大CG密度 0.83。
二、第二筆測資：ggctatacagtactaatCtTtTgcatggc 有最大CG密度為 12/29=0.41。(此時區段長度為 29)
出處
：
成大月賽 5th
(管理：tarco)
轉換成 01 字串，問題等價求最大平均值問題，
最大平均值問題，使用單調&斜率優化的方式去解，
證明方式轉換成幾何問題。
效率 O(n)
證明請網路搜一下這篇論文 算法合集之《浅谈数形结合思想在信息学竞赛中的应用》
/********************************************************************/
/* Problem: a639 "DNA Density" from 成大月賽 5th */
/* Language: C (1055 Bytes) */
/* Result: AC(4ms, 329KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2013-03-14 19:39:41 */
/********************************************************************/
#include <stdio.h>
#include <string.h>
double get_avg(int l, int r, int sum[]) {
return (double)(sum[r]-sum[l])/(r-l);
}
int main() {
int L, n;
char s[150];
int i, j, q[150];
while(scanf("%d %s", &L, s+1) == 2) {
int sum[150] = {};
n = strlen(s+1);
for(i = 1; s[i]; i++)
sum[i] = sum[i-1] +
(s[i] == 'C' || s[i] == 'c' || s[i] == 'G' || s[i] == 'g');
double ans = (double)sum[n]/n;
int front, rear;
front = 0, rear = -1;
for(i = L; i <= n; i++) {
int tmp = i-L;
while(front < rear && get_avg(q[rear], tmp, sum) <= get_avg(q[rear-1], q[rear], sum))
rear--;
q[++rear] = tmp;
while(front < rear && get_avg(q[front], i, sum) <= get_avg(q[front+1], i, sum))
front++;
double tans = get_avg(q[front], i, sum);
if(tans > ans)
ans = tans;
}
printf("%.2lf\n", ans + 1e-6);
}
return 0;
}
轉換成 01 字串，問題等價求最大平均值問題，
最大平均值問題，使用單調&斜率優化的方式去解，
證明方式轉換成幾何問題。
效率 O(n)
證明請網路搜一下這篇論文 算法合集之《浅谈数形结合思想在信息学竞赛中的应用》
/********************************************************************/
/* Problem: a639 "DNA Density" from 成大月賽 5th */
/* Language: C (1055 Bytes) */
/* Result: AC(4ms, 329KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2013-03-14 19:39:41 */
/********************************************************************/
#include <stdio.h>
#include <string.h>
double get_avg(int l, int r, int sum[]) {
return (double)(sum[r]-sum[l])/(r-l);
}
int main() {
int L, n;
char s[150];
int i, j, q[150];
while(scanf("%d %s", &L, s+1) == 2) {
int sum[150] = {};
n = strlen(s+1);
for(i = 1; s[i]; i++)
sum[i] = sum[i-1] +
(s[i] == 'C' || s[i] == 'c' || s[i] == 'G' || s[i] == 'g');
double ans = (double)sum[n]/n;
int front, rear;
front = 0, rear = -1;
for(i = L; i <= n; i++) {
int tmp = i-L;
while(front < rear && get_avg(q[rear], tmp, sum) <= get_avg(q[rear-1], q[rear], sum))
rear--;
q[++rear] = tmp;
while(front < rear && get_avg(q[front], i, sum) <= get_avg(q[front+1], i, sum))
front++;
double tans = get_avg(q[front], i, sum);
if(tans > ans)
ans = tans;
}
printf("%.2lf\n", ans + 1e-6);
}
return 0;
}