首页 > 专题系列 > Java解POJ > POJ 2509 Peter’s smokes [解题报告] Java
2013
11-11

POJ 2509 Peter’s smokes [解题报告] Java

Peter’s smokes

问题描述 :

Peter has n cigarettes. He smokes them one by one keeping all the butts. Out of k > 1 butts he can roll a new cigarette.

How many cigarettes can Peter have?

输入:

Input is a sequence of lines. Each line contains two integer numbers giving the values of n and k.

输出:

For each line of input, output one integer number on a separate line giving the maximum number of cigarettes that Peter can have.

样例输入:

4 3
10 3
100 5

样例输出:

5
14
124

解题代码:

//* @author: [email protected]
import java.util.*;
import java.math.*;

public class Main {
  static int S, H;
  static int []h = new int [51];
  static int []y = new int [51];
  static void deal()
  {
    int i, j, k;
    double dist, temp;
    for (i = 0; i <= S; i++)
    {
	k = 1;
	for (j = 0; j <= S; j++)
	 {
	  dist = -1;
	  for (k = 0; k < H; k++)
	  {
	   if (i == x[k] && j == y[k])
	    break;
           temp = Math.sqrt((double)((i - x[k]) * (i - x[k]) + (j - y[k]) * (j - y[k])));
	   dist = Math.max(dist, temp);
	  }
	  if (k < H || dist > S - i || dist > i || dist > S - j || dist > j)
	    continue;
	  System.out.println(i + " " + j);
	  return;
	}
     }
     System.out.println("poodle");
   }

   static void input()
   {
    int N, i;
    Scanner cin = new Scanner (System.in);
    N = cin.nextInt();
    while (N > 0)
    {
	S = cin.nextInt();
	H = cin.nextInt();
	for (i = 0; i < H; i++)
	{
           x[i] = cin.nextInt();
	   y[i] = cin.nextInt();
	}
	deal();
	N--;
     }
    }
	
  public static void main (String []args)
   {
 	input();
  }
 }

  1. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

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