当前位置：首页 > java >正文

【TUST“码蹄杯”编程之星】4.23 每日一题

java 2025/7/5 6:27:09

题目要求

在“NEIMARK”这座看似普通的IT校园深处，昏暗的走廊尽头传来铿锵的脚步声——又是一场生死未卜的编程较量。教练的声音像夜半敲门般，带着不容置疑的威严和淡淡嘲讽：“这里，没有旁观者，只有强者与被淘汰者。”
故事引子与角色设定
你以为这只是又一场平凡的集训？别傻了。地点：NEIMARK培训中心，传说这里隐藏着通往巅峰的秘密。对象：参与者们在各自的座位前如同幽灵般潜伏，每个人的身上都刻着一个数字——他们的技术水平 ai。教练：神秘而冷酷，唯有“强队”才能获得他那仿佛能洞悉人心的赞许。
悬念规则：何谓“强队”？
在这片充斥代码与不眠夜的战场上，队伍的“强度”被定义为：强度 = 队员数量 × 队伍中最低技能值换句话说，即便眼前有天赋异禀的高手，只要最弱之环拖了后腿，整个队伍就会陷入万丈深渊。教练的任务：找出能够“幸存”——也就是“强度”至少达到 x 的那些队伍。
核心任务
参加者：共有 n 位学生，每位的技能分别记作 a₁, a₂, …, aₙ。
分组要求：每个队伍至少一人；所有学生必须恪守“军令”，各就各位，不能落单。
目标：在最黑暗的夜晚，教练嗜血般地冷笑：“我想看见最多的强队——告诉我，能有多少支队伍能存活到明天？”

输入格式

n x —— 学生数 n (1 ≤ n ≤ 2·10⁵)，强度阈值 x (1 ≤ x ≤ 10⁹)
a₁ a₂ … aₙ —— n 位学生的技能值 (1 ≤ aᵢ ≤ 10⁹)

输出格式

输出一个整数——在教练的残酷审判下，最多能组成多少支“强队”。

输入数据：

100 1314
1 100 500 655 115 26 760 282 251 229 143 755 105 693 759 914 559 90 605 433 33 31 96 224 239 518 617 28 575 204 734 666 719 559 430 226 460 604 285 829 891 7 778 826 164 715 433 349 285 160 221 981 782 345 105 95 390 100 368 868 353 619 271 827 45 748 471 550 128 997 945 388 81 566 301 850 644 634 907 883 371 592 197 722 72 47 678 234 792 297 82 876 239 888 104 390 285 465 651 855 374 167 380

实现步骤

1.操作观察

一个队伍能否>=x取决于最低战力，容易观察出，战力低若想组队占用人数多，许多本来能成队的强者或许会被“拖累“导致队伍数量减少，因此贪心让高战力优先成队就是ac思路。

2.实现思路

读取 n 和 x 以及战力容器 a。
对a降序排列。
直接遍历数组，使用cnt计算当前可能成队人数，每成一队将cnt重置继续向下遍历。
输出最终队伍总数即可。

3.关键点说明

理论上可以对数组多次进行操作，但由于每次操作都会使 z 通过 AND 操作而只可能减少其有效位，从而降低后续 OR 的提升效果，所以最佳策略是不对 z 进行任何操作，直接取所有 a[i] | z 的最大值。
注意数据类型选用 64 位整型（i64），以应对 2^30 范围内整数的操作。

代码示例

// 不带T
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef __int128_t i128;
const int M = 1e9 + 7;
#define N 200005void solve()
{int n;i64 x;cin >> n >> x;vector<i64> a(n);for (int i = 0; i < n; i++)cin >> a[i];sort(a.begin(), a.end(), greater<i64>());i64 cnt = 0, ans = 0;for (auto s : a){cnt++;if (cnt * s >= x){ans++;cnt = 0;}}cout << ans;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();return 0;
}