题目描述

今天是万圣节！ Farmer John 要带奶牛们去参加化装舞会，但不幸的是他只有一套服装。这套服装恰好能容纳两头奶牛，且总长度不超过 $S$（$1 \leq S \leq 10^6$）。FJ 有 $N$ 头奶牛（$2 \leq N \leq 20,000$），编号为 $1 \ldots N$，其中第 $i$ 头奶牛的身长为 $L_i$（$1 \leq L_i \leq 10^6$）。如果两头不同奶牛的身长之和不超过服装长度 $S$，则它们可以一起穿这套服装。FJ 想知道有多少对不同的奶牛符合条件。

输入格式

• 第 1 行：两个空格分隔的整数 $N$ 和 $S$
• 第 2..N+1 行：第 $i+1$ 行包含一个整数 $L_i$

输出格式

• 第 1 行：一个整数，表示符合条件的奶牛对数（顺序无关）

输入数据示例 1

4 6  
3  
5  
2  
1  

输出数据示例 1

4  

来源

USACO 2008 年 1 月青铜题

解题思路提示

排序后使用双指针法：将奶牛按身长从小到大排序，用左指针指向最小元素，右指针指向最大元素。若两指针指向的奶牛身长之和 $\leq S$，则左指针右侧的所有元素与当前左指针元素的组合均有效（数量为右指针 - 左指针），左指针右移；否则右指针左移。通过线性扫描统计所有符合条件的对数。