首页 > ACM题库 > HDU-杭电 > HDU 2996-Pagination-二叉树-[解题报告]HOJ
2014
02-24

HDU 2996-Pagination-二叉树-[解题报告]HOJ

Pagination

问题描述 :

Google is one of the most popular web search engines in the world. Many chinese like it very much and use it frequently. But recently, China Internet Illegal Information Reporting Centre(CIIRC) strongly criticized Google for "violating China’s laws and regulations, contravening social morality and injuring public interest." At the same time, the Great Firewall blocked more and more world famous websites regardless of the complaints from internet users.

As worrying about that Google will also be blocked soon, you decide to eatablish your own web search engine named Googolplex((10)^(10^100)) and share it with other ACMers.

Unitl now the spider of your Googolplex has crawled so many web pages that the page will be too long to display all the search result in a single page. So it’s time to develop the pagination function for Googolplex.

Pagination is used for displaying a limited number of results on search engine results pages. As many nicely designed websites, the format of page numbers of your pagination should follow the specification below:


1. As demonstrated in the picture, the format of the page numbers consists of 7 parts. They are, from left to right: first page, left ellipsis, previous mark, middle pages, next mark, right ellipsis, last page. The middle pages part contains the current page that the user is visiting now(it’s "8" in the picutre). Please note that some of these parts will be hidden if the current page is some specific values.

2. For the first page part: It always displays "1". If the first page of middle pages part is equal to 1, this part should be hidden.

3. For the left ellipsis part: It always displays "…". If the first page of middle pages part is 2, or the first page part is hidden, this part should be hidden.

4. For the previous mark part: It always displays "<<". If the current page is 1, this part should be hidden.

5. For the middle pages part: It displays M numbers at most. If M is greater than T, the total number of pages, it displays T numbers. The position of the current page C should be M/2+1. So there are M/2 numbers before C and M-(M/2+1) after C. If the numbers before C is less than M/2, the middle pages part will shift to right to ensure there are M numbers displayed in total. If the numbers after C is less than M-(M/2+1), the middle pages part will shift to left to ensure there are M numbers displayed in total. Please refer to the sample for clarification.

6. For the next mark part: It always displays ">>". If the current page is equal to the last page, this part should be hidden.

7. For the right ellipsis part: It always displays "…". If the last page of middle pages part is one less than the total number of pages, or the last page part is hidden, this part should be hidden.

8. For the last page part: It always displays T, the total number of pages. If the last page of middle pages part is equal to T, this part should be hidden.

Given T, the total number of pages, M, the number of pages displayed in the middle pages part, and C, the current page that the user is visiting now, please write a program to generate the page numbers of pagination in the required format.

输入:

The input file contains several test cases. Each test case has a line containing three integers T (1 <= T <= 10^9), M (1 <= M <= 50), C (1 <= C <= T).
Input is terminated by a line contains "0 0 0".

输出:

The input file contains several test cases. Each test case has a line containing three integers T (1 <= T <= 10^9), M (1 <= M <= 50), C (1 <= C <= T).
Input is terminated by a line contains "0 0 0".

样例输入:

10 3 5
8 4 8
0 0 0

样例输出:

1 ... << 4 [5] 6 >> ... 10
1 ... << 5 6 7 [8]
Hint
For the second test case "8 4 8". The current page is 8, originally the middle pages part should display "6 7 8 9". But there are only 8 pages in total, so the middle pages part should shift one page to left, and display "5 6 7 8".

  KD树,来源计算几何,在《计算几何-算法与应用》一书中有详细的解释。

  这题是比较裸的KD树模型,要在点集中找到离一个点最近的一个点。其实KD树就是一棵多维平衡二叉树,将多维空间分成很多个部分,查找时能够较快的逼近查找点,从而快速的找到距离某点最近或者较近的点。

  在网上找到了这份模版,简洁高效。

  MARK一下URAL1369,也是一道KD树,目前TLE中。。。

#include <stdio.h>
 #include <string.h>
 #include <algorithm>
 #define MAXN 100005
 #define INF (1LL<<62)
 using namespace std;
 typedef long long LL;
 struct point{
     int x,y;
 }p[MAXN],p2[MAXN];
 bool dv[MAXN];
 bool cmpx(const point& p1,const point& p2){
     return p1.x<p2.x;
 }
 bool cmpy(const point& p1,const point& p2){
     return p1.y<p2.y;
 }
 LL getdis(point p1,point p2){
     return (LL)(p1.x-p2.x)*(p1.x-p2.x)+(LL)(p1.y-p2.y)*(p1.y-p2.y);
 }
 void buildKD(int l,int r,point p[]){
     if(l==r)return;
     int mid=(l+r)>>1;
     //按照坐标范围选择建树轴
     int minx=min_element(p+l,p+r,cmpx)->x;
     int miny=min_element(p+l,p+r,cmpy)->y;
     int maxx=max_element(p+l,p+r,cmpx)->x;
     int maxy=max_element(p+l,p+r,cmpy)->y;
     dv[mid]=(maxx-minx>=maxy-miny);
     //dv[mid]=(step&1);也可以按照层数交替建树,貌似效率略慢
     nth_element(p+l,p+mid,p+r,dv[mid]?cmpx:cmpy);
     buildKD(l,mid,p);
     buildKD(mid+1,r,p);
 }
 LL res=0;
 void find(int l,int r,point a,point p[]){
     if(l==r)return;
     int mid=(l+r)>>1;
     LL dist=getdis(a,p[mid]);
     if(dist>0)res=min(res,dist);
     LL d=dv[mid]?(a.x-p[mid].x):(a.y-p[mid].y);
     int l1=l,l2=mid+1,r1=mid,r2=r;
     if(d>0)swap(l1,l2),swap(r1,r2);
     find(l1,r1,a,p);
     if(d*d<res)find(l2,r2,a,p);
 }
 int n,cas;
 int main(){
     freopen("test.in","r",stdin);
     scanf("%d",&cas);
     while(cas--){
         scanf("%d",&n);
         for(int i=0;i<n;i++)
             scanf("%d%d",&p[i].x,&p[i].y),p2[i]=p[i];
         buildKD(0,n,p);
         for(int i=0;i<n;i++){
             res=INF;
             find(0,n,p2[i],p);
             printf("%I64d\n",res);
         }
 
 
     }
     return 0;
 }

 

  

解题参考:http://www.cnblogs.com/swm8023/archive/2012/09/04/2670258.html


  1. 3,求得所有的为的总和sum—->所有数的总和
    printf( "Not Possible" );—->printf("impossible");
    对吗?

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  4. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  5. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.