化装晚会

题目描述

万圣节又到了！乐乐打算带他的小羊去参加化装晚会，但是，乐乐只 做了一套能容下两头总长不超过S (1≤S≤1000000)的小羊恐怖服装。 乐乐养了N(2≤N≤20000)头按1--N顺序编号的小羊，编号为i的小羊的 长度为L_i(1≤L_i≤1000000)。如果两头小羊的总长度不超过S，那么 她们就能穿下这套服装。

乐乐想知道，如果他想选择两头不同的小羊来穿这套衣服，一共

有多少种满足条件的方案。

输入

第1行是2个整数：N和S；

第2～N+l行每行一个整数：L_i。

输出

1个整数，表示乐乐可选择的所有方案数。注意小羊顺序不同的两种方 案是被视为相同的。

样例输入 复制

4 6

3

5

2

1

样例输出 复制

4

提示

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,s,i,a[500010],t,w,mid,ans,bao;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>s;
	for(i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);
	for(i=1;i<n;i++){
		t=i+1;
		w=n;bao=-1;
		while(t<=w){
			mid=(t+w)/2;
			if(a[mid]+a[i]<=s)bao=mid,w=mid-1;
			else t=mid+1;
		}
		if(bao!=-1)ans+=bao-i+1;
	}
	cout<<ans;
	return 0;
}

4种选择分别为：小羊1和小羊3；小羊l和小羊4；小羊2和小羊4；小羊 3和小羊4。