首页 > 专题系列 > Java解POJ > POJ 3663 Costume Party [解题报告] Java
2013
11-13

POJ 3663 Costume Party [解题报告] Java

Costume Party

问题描述 :

It’s Halloween! Farmer John is taking the cows to a costume party, but unfortunately he only has one costume. The costume fits precisely two cows with a length of S (1 ≤ S ≤ 1,000,000). FJ has N cows (2 ≤ N ≤ 20,000) conveniently numbered 1..N; cow i has length Li (1 ≤ Li ≤ 1,000,000). Two cows can fit into the costume if the sum of their lengths is no greater than the length of the costume. FJ wants to know how many pairs of two distinct cows will fit into the costume.

输入:

* Line 1: Two space-separated integers: N and S
* Lines 2..N+1: Line i+1 contains a single integer: Li

输出:

* Line 1: A single integer representing the number of pairs of cows FJ can choose. Note that the order of the two cows does not matter.

样例输入:

4 6
3
5
2
1

样例输出:

4

解题代码:

//* @author: [email protected]
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int a=in.nextInt();
  int b=in.nextInt();
  ArrayList< Integer> arr=new ArrayList< Integer>();
  for(int i=0;i< a;i++)
	arr.add(in.nextInt());
  Collections.sort(arr);
  int count=0;
  for(int i=0;i< a-1;i++)
  {
	int l=b-arr.get(i);
	int min=i+1;
	int max=a-1;
	boolean bb=false;
	while(max>min)
	{
		int mid=(max+min)/2;
		if(arr.get(mid)>l) max=mid-1;
		else if(arr.get(mid)<=l) min=mid+1;
		bb=true;
		
	}
	if(bb)
	{
		if(arr.get(min)>l) count--;
		count+=min-i;
	}
	
    }
    System.out.println(count);
  }
}

  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。