题解与讨论区 1157: 张老师组队

题解与讨论区 1157: 张老师组队

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MB

返回问题页面

题目描述

    在张老师的学生中,每一名同学都有一个能力值。现在张老师想挑选一个两人小组,他有个奇怪的要求,
    需要这两名同学的能力值加起来和张老师一个期望的值一样,现在请你帮忙计算他有多少种挑选学生组成小组的方式,注意不同学生能力值可能相同。

第1157题的题解

重型榴弹手

Newbie 的题解


用 num[i]表示能力值为 i 的数字的出现次数,能力值为 i 的同学对于结果的贡献为 num[i] ·num[t-i],注意能力值相同时的贡献为 num[i] ·(num[i]-1)/2 (Cn2C_n^2)。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. constexpr int MAXN = 1e5 + 5, MOD = 1e9 + 7;
  4. int n, t;
  5. long long ans;
  6. array<int, MAXN> a, num;
  7. int main() {
  8. boost;
  9. cin >> n >> t;
  10. for (int i = 1; i <= n; i++) cin >> a[i], num[a[i]]++;
  11. for (int i = 0; i <= t / 2; i++) {
  12. if (i == t - i) ans += 1LL * num[i] * (num[i] - 1) / 2;
  13. else ans += 1LL * num[i] * num[t - i];
  14. }
  15. cout << ans << endl;
  16. return 0;
  17. }



点赞 1
举报