A182171.Yuilice 的糖盒配对
普及-
官方
通过率:0%
时间限制:1.50s
内存限制:256MB
题目描述
Yuilice 有 n 个糖盒,编号为 1 到 n,第 i 个盒子里有 ai 颗糖。
她想选出两个不同的盒子。在选出的两个盒子之间,每次可以把一颗糖从其中一个盒子移到另一个盒子,但不能移动盒中不存在的糖。她最多进行 k 次移动,也可以不移动。
如果能让选出的两个盒子最终拥有相同数量的糖,就称这两个盒子可以配对。其他盒子中的糖不能参与移动。
请计算有多少对盒子可以配对。按盒子的编号区分不同的盒对,(i,j) 和 (j,i) 只计一次;每一对盒子都从原来的糖果数量开始独立判断。
输入格式
第一行包含两个整数 n,k,分别表示糖盒数量和每一对盒子允许的最多移动次数。
第二行包含 n 个整数 a1,a2,…,an,其中 ai 表示第 i 个糖盒原有的糖果数量。
输出格式
输出一行一个整数,表示可以配对的盒对数量。
输入输出样例
输入#1
6 2 1 5 3 2 6 8
输出#1
5
输入#2
4 0 7 7 7 8
输出#2
3
说明/提示
样例 1 解释
可以配对的编号对为 (1,2)、(1,3)、(2,3)、(4,5) 和 (5,6)。
例如,第 1、2 个盒子原来分别有 1、5 颗糖。从第 2 个盒子向第 1 个盒子移动两颗糖后,两盒都为三颗。
第 4、6 个盒子分别有 2、8 颗糖,需要移动三次,超过限制。
样例 2 解释
不允许移动,只能选择原来糖果数量相同的两个盒子。前三个盒子中任选两个,共有三对。
数据范围
对于所有测试数据,2≤n≤2×105,0≤k≤109,0≤ai≤109。
| 测试点编号 | n |
|---|---|
| 1∼6 | 2≤n≤2000 |
| 7∼20 | 2≤n≤2×105 |
输入解题思路,AI测评打分。不知道怎么写?