poj3663 Costume Party

Costume Party

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 11793	Accepted: 4770

Description

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 hasN 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.

Input

* Line 1: Two space-separated integers: N and S

* Lines 2..N+1: Line i+1 contains a single integer: Li

Output

* 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.

Sample Input

4 6
3
5
2
1
      

Sample Output

4      

题意：给n个数字，从中任意选2个数字不大于s的可能有多少种

解题思路：先将数字从小到大排序，然后从最后开始向前遍历，如果当前遍历的数（第i个）和前一个数之和小于等于s，那么一定有i*(i-1)/2对数存在，接下来我们从i向后遍历，找到一个数与第i个数之和小于等于s，全部找出来即可，复杂度为O(nlgn)+O(n)

参考代码：

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 20000+2
int main(){
	int a[MAX],n,s;
	while (cin>>n>>s){
		for (int i=0;i<n;i++){
			cin>>a[i];
		}
		sort(a,a+n);
		int ans=0,k;
		for (k=n-1;k>0;k--){
			if (a[k]+a[k-1]<=s)
				break;
		}
		ans+=k*(k-1)/2;
		for (;k<n;k++){
			for (int i=0;i<k;i++){
				if (a[k]+a[i]<=s)
					ans++;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}