一、ZJ25 头条校招
描述：
头条的2017校招开始了！为了这次校招，我们组织了一个规模宏大的出题团队，每个出题人都出了一些有趣的题目，而我们现在想把这些题目组合成若干场考试出来，在选题之前，我们对题目进行了盲审，并定出了每道题的难度系统。一场考试包含3道开放性题目，假设他们的难度从小到大分别为a,b,c，我们希望这3道题能满足下列条件：
a<=b<=c
b-a<=10
c-b<=10
所有出题人一共出了n道开放性题目。现在我们想把这n道题分布到若干场考试中（1场或多场，每道题都必须使用且只能用一次），然而由于上述条件的限制，可能有一些考试没法凑够3道题，因此出题人就需要多出一些适当难度的题目来让每场考试都达到要求，然而我们出题已经出得很累了，你能计算出我们最少还需要再出几道题吗？
输入描述：
输入的第一行包含一个整数n，表示目前已经出好的题目数量。
第二行给出每道题目的难度系数d1,d2,…,dn。
数据范围
对于30%的数据，1 ≤ n,di ≤ 5;
对于100%的数据，1 ≤ n ≤ 10^5,1 ≤ di ≤ 100。
在样例中，一种可行的方案是添加2个难度分别为20和50的题目，这样可以组合成两场考试：（20 20 23）和（35,40,50）。
输出描述：
输出只包括一行，即所求的答案。
示例1
输入： 4
20 35 23 40
输出： 2
代码示例：
import java.io.*; import java.util.*; public class Main { private static int read(StreamTokenizer st) throws IOException{ st.nextToken(); return (int) st.nval; } public static void main(String[] args) throws IOException{ StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); //读取N int N = read(st); //读取数组 int[] arr = new int[N]; for(int i=0; i<N; i++){ arr[i] = read(st); } //数组排序 Arrays.sort(arr); //贪心 int pre=-1, size=0, cnt=0; int idx = 0; while(idx<N){ if(size==0){ pre = arr[idx++]; size=1; }else if(size==1){ int gap=arr[idx]-pre; if(gap>10 && gap<=20){ cnt++; size=0; idx++; }else if(gap>20){ cnt += 2; size=1; pre = arr[idx++]; }else{ pre = arr[idx++]; size = 2; } }else{ int gap=arr[idx]-pre; if(gap>10){ cnt++; pre = arr[idx++]; size=1; }else{ size=0; idx++; } } } if(size==1){ cnt +=2; }else if(size==2){ cnt +=1; } System.out.println(cnt); } }
ZJ19 万万没想到之抓捕孔连顺
描述：
我叫王大锤，是一名特工。我刚刚接到任务：在字节跳动大街进行埋伏，抓捕恐怖分子孔连顺。和我一起行动的还有另外两名特工，我提议
我们在字节跳动大街的 N 个建筑中选定 3 个埋伏地点。
为了相互照应，我们决定相距最远的两名特工间的距离不超过 D 。
我特喵是个天才! 经过精密的计算，我们从X种可行的埋伏方案中选择了一种。这个方案万无一失，颤抖吧，孔连顺！
……
万万没想到，计划还是失败了，孔连顺化妆成小龙女，混在cosplay的队伍中逃出了字节跳动大街。只怪他的伪装太成功了，就是杨过本人来了也发现不了的！
请听题：给定 N（可选作为埋伏点的建筑物数）、 D（相距最远的两名特工间的距离的最大值）以及可选建筑的坐标，计算在这次行动中，大锤的小队有多少种埋伏选择。
注意：
两个特工不能埋伏在同一地点
三个特工是等价的：即同样的位置组合( A , B , C ) 只算一种埋伏方法，不能因“特工之间互换位置”而重复使用
数据范围： 0 < n,d>= 10^6
输入描述：
第一行包含空格分隔的两个数字 N和D(1 ≤ N ≤ 1000000; 1 ≤ D ≤ 1000000)
第二行包含N个建筑物的的位置，每个位置用一个整数（取值区间为[0, 1000000]）表示，从小到大排列（将字节跳动大街看做一条数轴）
输出描述：
一个数字，表示不同埋伏方案的数量。结果可能溢出，请对 99997867 取模
示例1
输入：4 3
1 2 3 4
输出：4
说明：
可选方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)
示例2
输入：5 19
1 10 20 30 50
输出：1
说明：
可选方案 (1, 10, 20)
示例3
输入：2 100
1 102
输出：0
说明：
无可选方案
代码示例：
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); int d = sc.nextInt(); int[] locations = new int[n]; for (int i = 0; i < n; i++) { locations[i] = sc.nextInt(); } long count = dsp(locations, n, d); System.out.println(count); } } public static long dsp(int[] locations, int n, int d) { int left = 0, right = 2; long count = 0; int mod = 99997867; while (right < n) { if (locations[right] - locations[left] > d) left++; else if (right - left < 2) right++; else { long num = right - left; // 第二位和第三位之间的最远距离 count += num * (num - 1) / 2L; // 第二位和第三位可以排列组合的数量 right++; } } count %= mod; return count; } }
