第一題:染色問題(NOIP 2009模擬試験問題)
せんしょくもんだい
問題の説明:
0から10000000までの数軸があり、最初の色は白です.今ではその中の1段を黒や白に染め続け、全部でN段(1<=N<=5000)に染めている人がいます.あなたの任務はプログラムを作成して、最後に最も長い白いセグメントを見つけることです.
入力:最初の行は1つの数Nしかありません.次のN行は、ai bi ciというフォーマットで、1つのセグメントを染めるたびに情報です.
ai、biは整数、ciは記号「b」または「w」の3つをスペースで区切って、今回aiからbiに染められたことを示し、使用色はci('w’は白、'b’は黒)で、0出力:2つの数x,y(x<=y)のみで、最も長い白いセグメントをスペースで区切ります.複数の解があればXの最小の解を出力する.
入出力サンプル
dye.in
dye.out
4 1 999999997 b 40 300 w 300 634 w 43 47 b
48 634
問題の説明:
0から10000000までの数軸があり、最初の色は白です.今ではその中の1段を黒や白に染め続け、全部でN段(1<=N<=5000)に染めている人がいます.あなたの任務はプログラムを作成して、最後に最も長い白いセグメントを見つけることです.
入力:最初の行は1つの数Nしかありません.次のN行は、ai bi ciというフォーマットで、1つのセグメントを染めるたびに情報です.
ai、biは整数、ciは記号「b」または「w」の3つをスペースで区切って、今回aiからbiに染められたことを示し、使用色はci('w’は白、'b’は黒)で、0
入出力サンプル
dye.in
dye.out
4 1 999999997 b 40 300 w 300 634 w 43 47 b
48 634
/******************************************************************************************************
** Copyright (C) 2011.07.01-2013.07.01
** Author: famousDT <[email protected]>
** Edit date: 2011-10-17
******************************************************************************************************/
#include <stdio.h>
#include <stdlib.h>//abs,atof(string to float),atoi,atol,atoll
#include <math.h>//atan,acos,asin,atan2(a,b)(a/b atan),ceil,floor,cos,exp(x)(e^x),fabs,log(for E),log10
#include <vector>
#include <queue>
#include <map>
#include <time.h>
#include <set>
#include <list>
#include <stack>
#include <string>
#include <iostream>
#include <assert.h>
#include <string.h>//memcpy(to,from,count
#include <ctype.h>//character process:isalpha,isdigit,islower,tolower,isblank,iscntrl,isprll
#include <algorithm>
using namespace std;
//typedef long long ll;
#define MY_PI acos(-1)
#define MY_MAX(a, b) ((a) > (b) ? (a) : (b))
#define MY_MIN(a, b) ((a) < (b) ? (a) : (b))
#define MY_MALLOC(n, type) ((type *)malloc((n) * sizeof(type)))
#define MY_ABS(a) (((a) >= 0) ? (a) : (-(a)))
#define MY_INT_MAX 0x7fffffff
/*==========================================================*\
| noip
\*==========================================================*/
struct segment
{
int low;
int high;
} seg[100005], tmp[100005];
bool cmp(segment a, segment b)
{
return a.low < b.low;
}
int main()
{
FILE *in, *out;
in = freopen("dye.in", "r", stdin);
out = freopen("dye.out", "w", stdout);
int n;
int i, j, k, a, b;
int index = 1;
char c;
scanf("%d", &n);
seg[0].low = 0;
seg[0].high = 1000000000;
for (k = 0; k < n; ++k) {
scanf("%d%d %c", &a, &b, &c);
if (c == 'w') {// ，
int pos = 0;
seg[index].low = a;
seg[index].high = b;
++index;
sort(seg, seg + index, cmp);
int t_low = seg[0].low;
int t_high = seg[0].high;
for (i = 0; i < index; ++i) {
if (seg[i].low <= t_high) {
if (seg[i].high > t_high) {
t_high = seg[i].high;
}
} else {
seg[pos].low = t_low;
seg[pos++].high = t_high;
t_low = seg[i].low;
t_high = seg[i].high;
}
}
seg[pos].low = t_low;
seg[pos++].high = t_high;
index = pos;
} else {// ，
int pos = 0;
for (i = 0; i < index; ++i) {
if (seg[i].high < a || seg[i].low > b) {
tmp[pos].low = seg[i].low;
tmp[pos].high = seg[i].high;
++pos;
} else if (seg[i].low >= a && seg[i].high <= b) {
;
} else if (seg[i].low >= a && seg[i].high > b) {
tmp[pos].low = b + 1;
tmp[pos].high = seg[i].high;
++pos;
} else if (seg[i].low < a && seg[i].high <= b) {
tmp[pos].low = seg[i].low;
tmp[pos].high = a - 1;
++pos;
} else if (seg[i].low < a && seg[i].high > b) {
tmp[pos].low = seg[i].low;
tmp[pos].high = a - 1;
++pos;
tmp[pos].low = b + 1;
tmp[pos].high = seg[i].high;
++pos;
}
}
for (i = 0; i < pos; ++i) {
seg[i].low = tmp[i].low;
seg[i].high = tmp[i].high;
}
index = pos;
}
}
int max = -1;
int ans;
for (i = 0; i < index; ++i) {
int t = seg[i].high - seg[i].low;
if (t > max) {
max = t;
ans = i;
}
}
printf("%d %d
", seg[ans].low, seg[ans].high);
system("pause");
return 0;
}
/*
4
1 999999997 b
40 300 w
300 634 w
43 47 b
*/