首页 > 专题系列 > Java解POJ > POJ 1819 Disks [解题报告] Java
2013
11-10

POJ 1819 Disks [解题报告] Java

Disks

问题描述 :

Consider N floating point numbers N representing the radii of N disks. We fix a disk in the xOy system, if we position it at a positive coordinate x (big enough), tangential to the 0x axis and above it and after that we push it to 0y until it becomes tangent to 0y or to the first disk that it meets on the way. In the configuration that results by fixing in order all the given disks, some of them can be considered as being dispensible, because, if we eliminate them, the total width of the configuration is the same, which means that there is no disk that can be moved to the left.



Identify all the indispensible disks for a given configuration (in the configuration from above; the gray disks are dispensible).

输入:

The input has the following structure:
  • the first line contains N ( N <= 1000), the number of disks;
  • the next N lines contain N real numbers representing the radii of the disks, in the order they are fixed in the configuration.

输出:

The output will have the following structure:
  • the first line will contain an integer K, representing the number of dispensable disks;
  • each of the next K lines will contain the order number of the dispensable disks.

样例输入:

7
4
0.1
0.5
3
0.5
4
1 

样例输出:

3
2
3
5

解题代码:

import java.io.BufferedReader;  
import java.io.InputStreamReader;  
  
public class Main{  
  
    static double r[],x[];  
    static int touch[];  
    static boolean flag[];  
      
    public static void main(String[] args) throws Exception{  
          
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));  
          
        int n = Integer.parseInt(buf.readLine());  
          
        r = new double[n];  
        x = new double[n];  
        touch = new int[n];  
        flag = new boolean[n];  
        double max = 0;  
        int tmax = 0;  
        java.util.Arrays.fill(touch, -1);  
          
        for(int i=0;i< n;i++){  
            r[i] = Double.parseDouble(buf.readLine());  
            x[i] = r[i];  
        }  
          
      for(int i=1;i< n;i++){  
        for(int j=0;j< i;j++){  
         if(x[j]+2*Math.sqrt(r[i]*r[j])-x[i]>1e-10){//2*Math.sqrt(r[i]*r[j])是i,j圆心的水平距离 即x坐标差值   
                    x[i] = x[j]+2*Math.sqrt(r[i]*r[j]);  
                    touch[i] = j;  
                }  
            }  
              
            if(x[i]+r[i]-max>1e-10){  
                max = x[i]+r[i];  
                tmax = i;  
            }  
        }  
        int sum = 0;  
        for(int i=1;i< n;i++){  
            for(int j=touch[i]+1;j< i;j++)  
                if(!flag[j]){  
                    flag[j] = true;  
                    sum ++;  
                }  
        }  
          
        for(int i=tmax+1;i< n;i++)  
            if(!flag[i]){  
                flag[i] = true;  
                sum ++;  
            }  
          
        System.out.println(sum);  
        for(int i=0;i< n;i++)  
            if(flag[i])  
                System.out.println(i+1);  
  
    }  
  
}

  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  2. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  3. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  4. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  5. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  6. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?