poj3663 Costume Party-白红宇

poj3663 Costume Party

阅读量：2439 次

发布时间：2019-05-10

本文共 1300 字，大约阅读时间需要 4 分钟。

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 L_i (1 ≤ L_i ≤ 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: L_i

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 63521

Sample Output

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

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

参考代码：

#include 
   
    #include 
    
     using namespace std;#define MAX 20000+2int main(){	int a[MAX],n,s;	while (cin>>n>>s){		for (int i=0;i
     
      >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

转载地址：http://hfbqb.baihongyu.com/

你可能感兴趣的文章