离散化入门

离散化：只关心数据的大小，不关心规模长度。

一个最简单的例子：

锻炼计划(exercise.pas)

身体是革命的本钱，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 10 1 Basketball 1 10 1 Output Accepted 1440

Input 1 1 Nunchakus 1 1 2 Output Runtime Error 1 约定 0 < n < =2^31-1 0 < = m < =500 所有中间值的绝对值不会超过2^31-1 每一个锻炼项目的名称不超过20个字符，其中不含空格。

题解： 我们可以扫一遍所有分钟，模拟即可。

#include<iostream> #include<cstdio> #include<algorithm> #define mn 1440 using namespace std; int st,m; struct P{ char s[25]; int b,e,t; }p; int fg[1500]; int main() { scanf("%d%d",&st,&m); for(int i=1;i<=m;i++) { scanf("%s",&p.s); scanf("%d%d%d",&p.b,&p.e,&p.t); for(int j=p.b;j<=p.e;j++) { fg[j]=p.t; } } for(int i=1;i<=mn;i++) { st++; if(fg[i]>0) st-=fg[i]; if(st<=0) { cout<<"Runtime Error"<<endl; cout<<i<<endl; return 0; } } cout<<"Accepted"<<endl<<st<<endl; }

如果一天有多少分钟数1440这个数记为mx>10^7,这道题就得离散化。 但是如果我们对开始时间的大小进行关键字排序，那么可以说就把整天的计划全部映射在了一个数轴上，我们不关心第几分钟，只关心有几段在当前项目的前面。这样就实现了对数据的离散。然后再进行扫描，复杂度为O(mlogm+m)。从而在复杂度上进行了一个提升。 代码中的500可以换成10^6以下级别。

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; int st,m,sm[1505]; struct P{ char s[25]; int b,e,t; }p[505]; bool cmp(P x,P y) { return x.b<y.b; } int main() { scanf("%d%d",&st,&m); for(int i=1;i<=m;i++) { scanf("%s",&p[i].s); scanf("%d%d%d",&p[i].b,&p[i].e,&p[i].t); //求一个前缀和 sm[i]+=p[i].t*(p[i].e-p[i].b+1); } sort(p+1,p+m+1,cmp); for(int k=1;k<=m;k++)//o(m<=500) { if((st+p[k].e-sm[k])<=0) { cout<<"Runtime Error"<<endl; int pe=ceil((st+p[k].b-sm[k-1])/p[k].t); cout<<p[k].b+pe-1<<endl; return 0; } } cout<<"Accepted"<<endl<<st+1440-sm[m]<<endl; }

P1496 vijos1165 火烧赤壁 /2005普及组 校门外的树

题目描述

曹操平定北方以后，公元208年，率领大军南下，进攻刘表。他的人马还没有到荆州，刘表已经病死。他的儿子刘琮听到曹军声势浩大，吓破了胆，先派人求降了。

孙权任命周瑜为都督，拨给他三万水军，叫他同刘备协力抵抗曹操。

隆冬的十一月，天气突然回暖，刮起了东南风。

没想到东吴船队离开北岸大约二里距离，前面十条大船突然同时起火。火借风势，风助火威。十条火船，好比十条火龙一样，闯进曹军水寨。那里的船舰，都挤在一起，又躲不开，很快地都烧起来。一眨眼工夫，已经烧成一片火海。

曹操气急败坏的把你找来，要你钻入火海把连环线上着火的船只的长度统计出来！

输入输出格式

输入格式： 第一行：N

以后N行，每行两个数：Ai Bi(表示连环线上着火船只的起始位置和终点,-10^9<=Ai,Bi<=10^9)

输出格式： 输出着火船只的总长度

输入输出样例

输入样例#1： 3 -1 1 5 11 2 9 输出样例#1： 11 说明

n<=20000

如果Ai=Bi是一个点则看作没有长度

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; struct P{ int l,r; }p[20005]; bool cmp(P x,P y) { return x.l<y.l; } P sp; int n,len; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&p[i].l ,&p[i].r); } sort(p+1,p+n+1,cmp); sp.l =p[1].l,sp.r=p[1].r; for(int i=2;i<=n;i++) { if(p[i].l>sp.r) len+=sp.r-sp.l,sp.l=p[i].l,sp.r=p[i].r; else if(p[i].r >sp.r) { sp.r=p[i].r; } } len+=sp.r-sp.l; cout<<len<<endl; }

接着做图形面积题目：http://blog.csdn.net/ivy_uu/article/details/53039481