在OI界还是占有一定地位的，而很多的离散化题目有很大程度上是贪心，也有很多是动态规划。离散是将数据经过关键字排序后以NP类问题处理。离散化是程序设计中一个非常常用的技巧，它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中“只考虑我需要用的值”。离散化可以改进一个低效的算法，甚至实现根本不可能实现的算法。要掌握这个思想，必须从大量的题目中理解此方法的特点。下面我从易到难选择了一些题目，希望对大家有所帮助。
离散化的定义如下：把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
其基本思想很简单，就是当输入数据的范围是无限空间，或者输入数据有很大量重复时，可以作一映射，从输入的无限空间到逻辑上的有限、有序的空间、同时避免重复。
声明：由于noip2005第二题river有很多版本的题解，故不在此篇中进行讲解。
本文章中有某些非原创部分，版权属于原作者。
锻炼计划(exercise.pas) noip普及组难度
身体是革命的本钱，OIers不要因为紧张的学习和整天在电脑前而忽视了健康问题。小x设计了自己的锻炼计划，但他不知道这个计划是否可行，换句话说如果计划不当可能会让他的体力超支，所以小x请你帮助他。
一天有1440分钟，所以小x列出的是这一整天第1至第1440分钟的计划。小x的体力用一个整数来表示，他会按照计划表进行锻炼，同时，每分钟小x的体力会自动增加1。如果某一分钟末小x的体力小于等于零，那么可怜的小x就累死了……
输入(exercise.in)
第一行是用空格分开的两个整数n,m，分别表示小x的初始体力值和计划的项目数量。
从第二行开始的m行，每行描述一个锻炼项目：名称、开始时间a、结束时间b、每分钟耗费的体力(用空格分隔)，表示此项目从第a分钟初开始，第b分钟末结束。锻炼项目按照开始时间递增顺序给出，不会出现两个项目时间冲突的情况。
输出(exercise.out)
输出包括两行，如果计划可行，第一行输出"Accepted"，第二行输出这一天过后最后剩余的体力；否则在第一行输出"Runtime Error"，第二行输出在第几分钟累死。
样例
Input
| Output
|
10 1
Basketball 1 10 1
| Accepted
1440
|
1 1
Nunchakus 1 1 2
| Runtime Error
1
|
约定
0<n<=2^31-1
0<=m<=500
所有中间值的绝对值不会超过2^31-1
每一个锻炼项目的名称不超过20个字符，其中不含空格。
题解：此题十分简单，来源为唐山OI 2005noip模拟赛的第一题，可以说是一个送分题目，如果每次查找开始锻炼最小的时刻，加上判断，复杂度为O(m^2)。但是如果我们对开始时间的大小进行关键字排序，那么可以说就把整天的计划全部映射在了一个数轴上，这样就实现了对数据的离散。然后再进行扫描，复杂度为O(mlogm+m)。从而在复杂度上进行了一个提升，当然，此题中数据范围较小，前者就可以AC。
program exercise;
const
success='Accepted';
failed='Runtime Error';
var
n,m,i,j:longint;
a:array[1..1440,1..2] of integer;
h,time:array[1..1440] of longint;
ch:char;
inf,outf:text;
procedure print1;
begin
assign(outf,'exercise.out');
rewrite(outf);
writeln(outf,failed);
writeln(outf,i);
close(outf);
end;
procedure init;
begin
assign(inf,'exercise.in');
reset(inf);
readln(inf,n,m);
for i:=1 to m do
begin
ch:='x';
while ch<>' ' do read(inf,ch);
readln(inf,a[i,1],a[i,2],h[i]);
end;
close(inf);
end;
procedure main;
begin
for i:=1 to m do
for j:=a[i,1] to a[i,2] do
time[j]:=h[i];
for i:=1 to 1440 do
if time[i]=0
then inc(n)
else
begin
inc(n);
n:=n-time[i];
if n<=0 then
begin
print1;
halt;
end;
end;
end;
procedure print;
begin
assign(outf,'exercise.out');
rewrite(outf);
writeln(outf,success);
writeln(outf,n);
close(outf);
end;
begin
init;
main;
print;
end.
火烧赤壁（vijos某次模拟赛题目noip2004校门口外的树加强版）略高于noip普及组难度
描述 Description
曹操平定北方以后，公元208年，率领大军南下，进攻刘表。他的人马还没有到荆州，刘表已经病死。他的儿子刘琮听军声势浩大，吓破了胆，先派人求降了。
孙权任命周瑜为都督，拨给他三万水军，叫他同刘备协力抵抗曹操。
隆冬的十一月，天气突然回暖，刮起了东南风。
没想到东吴船队离开北岸大约二里距离，前面十条大船突然同时起火。火借风势，风助火威。十条火船，好比十条火龙一样，闯进曹军水寨。那里的船舰，都挤在一起，又躲不开，很快地都烧起来。一眨眼工夫，已经烧成一片火海。
曹操气急败坏的把你找来，要你钻入火海把连环线上着火的船只的长度统计出来！
输入格式 Input Format
第一行：N
以后N行，每行两个数：Ai Bi(表示连环线上着火船只的起始位置和终点,-10^9<=Ai,Bi<=10^9)
输出格式 Output Format
输出着火船只的总长度
样例输入 Sample Input
3
-1 1
5 11
2 9
样例输出 Sample Output
11
注释 Hint
n<=20000
如果Ai=Bi是一个点则看作没有长度
题解：OI题目特点就是这样，同样的一个题目，数据范围变化，就不能说他们是一道题目。这道题目无法用朴素做法AC，而用离散化处理就降低了复杂度。思想是将其映射到数轴上，仅对每个线段的端点进行处理。
首先按照连环线的起点进行排序，将线段映射到数轴当中。设L为当前的总长度，a、b为所处理时找出的相接线段的起点和终点，对于第i条线段，因为进行过起点的排序，第i条线段的起点不可能小于a。如果起点在a,b之间，将b的值更新为第i条线段的终点值。如果起点值大于b，则将L更新为L和a到b之间的长度和。再将a值更新为第i条线段的起点位置。这样的算法复杂度就变成了O(nlogn+n)
隐形的翅膀 接近noip提高组难度
背景 Background
小杉终于进入了天堂。他看到每个人都带着一双隐形翅膀，他也想要。
（小杉是怎么看到的？……）
描述 Description
天使告诉小杉，每只翅膀都有长度，两只翅膀的长度之比越接近黄金分割比例，就越完美。
现在天使给了小杉N只翅膀，小杉想挑出一对最完美的。
输入格式 Input Format
每组测试数据的
第一行有一个数N(2<=N<=30000)
第二行有N个不超过1e5的正整数，表示N只翅膀的长度。
20%的数据N<=100
输出格式 Output Format
对每组测试数据输出两个整数，分两行，表示小杉挑选出来的一对翅膀。
注意，比较短的在前，如果有多对翅膀的完美程度一样，请输出最小的一对。
样例输入 Sample Input
4
2 3 4 6
样例输出 Sample Output
2
3
时间限制 Time Limitation
每个测试点1s
注释 Hint
你可以认为黄金分割比就是0.6180339887498949
题解：朴素复杂度为O(n^2)，进行排序后，将数据映射到一个数组当中后，数据呈现单调性，匹配的时候一旦不符合，就可以跳出循环，这样进行省去了多余的判断，复杂度就降到O（nlogn）了 。思想为将数映射到数轴上，利用单调性避免重复的运算。
源程序
program P1237;
const gold:real=0.6180339887498949;
var n,i,j,t1,t2:longint;
a:array[1..30000] of longint;
min,k:real;
procedure qsort(q,w:longint);{快排}
var e,r,t,y:longint;
begin
e:=a[(q+w) div 2];
r:=q;
t:=w;
repeat
while a[r]<e do inc(r);
while a[t]>e do dec(t);
if r<=t then
begin
y:=a[r];
a[r]:=a[t];
a[t]:=y;
inc(r);
dec(t);
end;
until r>t;
if r<w then qsort(r,w);
if t>q then qsort(q,t);
end;
begin
readln(n);
for i:=1 to n do
read(a[i]);
qsort(1,n);{排序}
min:=9999999;
i:=1;j:=2;{开始遍历翅膀}
repeat
k:=a[i]/a[j]-gold;{算比例}
if abs(k)<min then begin min:=abs(k);t1:=i;t2:=j;end;
if k>0 then inc(j) else inc(i);{如果前翅膀比后翅膀大于GOLD，换下一个翅膀（翅膀是递增的）}
while (a[j]=0) do inc(j);
until j>n;
writeln(a[t1]);
writeln(a[t2])
end.
