A182171.Yuilice 的糖盒配对

普及-

官方

通过率:0%

时间限制:1.50s

内存限制:256MB

题目描述

Yuilice 有 nn 个糖盒,编号为 11 到 nn,第 ii 个盒子里有 aia_i 颗糖。

她想选出两个不同的盒子。在选出的两个盒子之间,每次可以把一颗糖从其中一个盒子移到另一个盒子,但不能移动盒中不存在的糖。她最多进行 kk 次移动,也可以不移动。

如果能让选出的两个盒子最终拥有相同数量的糖,就称这两个盒子可以配对。其他盒子中的糖不能参与移动。

请计算有多少对盒子可以配对。按盒子的编号区分不同的盒对,(i,j)(i,j) 和 (j,i)(j,i) 只计一次;每一对盒子都从原来的糖果数量开始独立判断。

输入格式

第一行包含两个整数 n,kn,k,分别表示糖盒数量和每一对盒子允许的最多移动次数。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,其中 aia_i 表示第 ii 个糖盒原有的糖果数量。

输出格式

输出一行一个整数,表示可以配对的盒对数量。

输入输出样例

  • 输入#1

    6 2
    1 5 3 2 6 8
    

    输出#1

    5
    
  • 输入#2

    4 0
    7 7 7 8
    

    输出#2

    3
    

说明/提示

样例 1 解释

可以配对的编号对为 (1,2)(1,2)、(1,3)(1,3)、(2,3)(2,3)、(4,5)(4,5) 和 (5,6)(5,6)。

例如,第 11、22 个盒子原来分别有 11、55 颗糖。从第 22 个盒子向第 11 个盒子移动两颗糖后,两盒都为三颗。

第 44、66 个盒子分别有 22、88 颗糖,需要移动三次,超过限制。

样例 2 解释

不允许移动,只能选择原来糖果数量相同的两个盒子。前三个盒子中任选两个,共有三对。

数据范围

对于所有测试数据,2≤n≤2×1052\le n\le 2\times 10^5,0≤k≤1090\le k\le 10^9,0≤ai≤1090\le a_i\le 10^9。

测试点编号 nn
1∼61\sim 6 2≤n≤20002\le n\le 2000
7∼207\sim 20 2≤n≤2×1052\le n\le 2\times 10^5

输入解题思路,AI测评打分。不知道怎么写?

首页