化装晚会

题目描述

万圣节又到了！Farmer John打算带他的奶牛去参加一个化装晚会，但是，FJ只做了一套能容下两头总长不超过S(1 < = S < = 1,000,000)的牛的恐怖服装。FJ养了N(2 < = N < = 50,000)头按1…N顺序编号的奶牛，编号为i的奶牛的长度为L_i(1 < = L_i < = 1,000,000)。如果两头奶牛的总长度不超过S，那么她们就能穿下这套服装。
FJ想知道，如果他想选择两头不同的奶牛来穿这套衣服，一共有多少种满足条件的方案。

输入
输入文件的第1行是 2个用空格隔开的整数：N 和 S， 第2…N+1行每行一个整数：L_i

输出
1行: 输出1个整数，表示FJ可选择的所有方案数。注意奶牛顺序不同的两种方案是被视为相同的

输入样例
4 6
3
5
2
1

输出样例
4

说明
输出说明: 4种选择分别为：奶牛1和奶牛3；奶牛1和奶牛4；奶牛2和奶牛4；奶牛3和 奶牛4。

【数据规模】
对于30%的数据，N<=10000;
对于100%的数据，N<=50000;
.
.
.
.
.
分析
先从小到大排序
对于每一头奶牛，二分出它所能加的最大值的位置
由此即可算出有多少种方案
.
.
.
.
.
程序：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int x,n,s,a[60000];

int work(int l,int r)
{
	if (l>r) return r;
	int mid=(l+r)/2;
	if (x+a[mid]<=s) return work(mid+1,r); else return work(l,mid-1);
}

int main()
{
	scanf("%d%d",&n,&s);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for (int i=1;i<=n;i++)
		if (a[i]>s)
		{
			n=i-1;
			break;
		}
	int ans=0;
	for (int i=1;i<n;i++)
	{
		x=a[i];
		int wz;
		if (x+a[i+1]<=s) wz=work(i+1,n); else break;
		ans+=wz-i;
	}
	cout<<ans;
	return 0;
}