集訓(xùn)隊(duì)作業(yè)happy解題報(bào)告

1、Happy 問題解題一、 算法描述一個(gè)平行于坐標(biāo)軸的矩形是由其左上角坐標(biāo)和右下角坐標(biāo)決定的，而一個(gè)坐標(biāo)有x 坐標(biāo)和 y 坐標(biāo)兩個(gè)，所以一個(gè)矩形是由四個(gè)量共同決定的。如果簡(jiǎn)單采用離散化的思路，必須首先確定它的左 x 坐標(biāo)和右 x 坐標(biāo)，最后在一次掃描中確定y 坐標(biāo)，時(shí)間復(fù)雜度為被選取的點(diǎn)都對(duì)由它和右邊界確定的最大矩形沒有影響，因而可以被刪除。如果用有序表來保存所有的y 坐標(biāo)，則在刪除這些無用節(jié)點(diǎn)后，最大矩形的上下邊界由該點(diǎn)的前驅(qū)點(diǎn)和后繼點(diǎn)分別決定。如果在實(shí)現(xiàn)過程中采用靜態(tài)實(shí)現(xiàn)雙向鏈表的方法，并且引入散列對(duì)每一個(gè) y 坐標(biāo)值在鏈表中進(jìn)行定位，則找出最大矩形，并該結(jié)構(gòu)的事件復(fù)雜度為W,L,n;lon

2、g ans;datmaxn2;/ hashmaxl+1;/line所有點(diǎn)的信息所有存在的y 坐標(biāo)，hash所有 y 坐標(biāo)在 line 中的listmaxn3,mapmaxn;/list了當(dāng)前右邊界左邊的所有 y 坐標(biāo)，/其中，lista0y 坐標(biāo)的值，/lista1,lista2分別其當(dāng)前的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)/map了一個(gè)點(diǎn)在 list 中的對(duì)應(yīng)位置void qsort(a,b);/以 x 坐標(biāo)為第一序，y 坐標(biāo)為第二序?qū)λ悬c(diǎn)坐標(biāo)排序inline long max(long a,long b)return ab?a:b;main()tol,i;n=1;m=0; finWLtol; for (

3、i=0;iab;if (!a|!b|a=W|b=L) continue;/所有在地圖邊緣的點(diǎn)可以不用考慮 datn0=a;datn1=b;n+;datn0=W;datn1=L;n+;/加入一個(gè)虛擬點(diǎn) qsort(1,n-1);/排序memsesh,0,sizeof(hash);for (i=1;in;)/移動(dòng)右邊界memset(list,0,sizeof(list); memset(map,0,sizeof(map); list00=0;list01=-1;/加入虛擬 y=0 的坐標(biāo)t=0,j;for (j=1;jL;j+)if (hashj)/該 y 坐標(biāo)出現(xiàn)在當(dāng)前右邊界的左邊ans=max

4、(ans,(long(j)-listt0)*dati0);listt2=t+1;t+;listt0=j;listt1=t-1;/加入到 y 坐標(biāo)列表，并計(jì)算新面積maphashj=t;/建立點(diǎn)到 y 坐標(biāo)列表的對(duì)應(yīng)方式ans=max(ans,(long(L)-listt0)*dati0);listt2=t+1;t+;listt0=L;listt1=t-1;listt2=-1;/加入 y=L 的虛擬點(diǎn)for (j=1;ji;j+)/移動(dòng)左邊界if (!mapj) continue;/該點(diǎn)不在當(dāng)前需要處理的 y 坐標(biāo)列表中x=mapj,x0=listx1,x1=listx2; ans=max(ans,(long(listx10)-listx00)*(dati0-datj0); listx02=x1;listx11=x0;/將點(diǎn) x 從 y 坐標(biāo)列表中脫鉤dohashdati1=i;/將點(diǎn) i 加入已出現(xiàn)集合i+;/移動(dòng)右邊界while (in&dati0=dati-10);fouans=b) return; x=dat(a+b)/20,i=a,j=b;while (i=j)while (dati0 x) j-; if (i=j)t=dati0;da