会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
(x+t)(y+t) 为偶数，当且仅当 x+t 与 y+t 里至少有一个偶数。把货签按 vi+t 的奇偶分成偶类和奇类。
- 两个奇类乘积必为奇数，不能编档。奇类只能配偶类。
- 偶类与任何人都能编档，偶类之间也可以互配。
- 因此最优策略是：若奇类更多，把全部偶类拿去配奇类，档数为偶类个数；否则先把奇类配完，剩下的偶类两两互配，档数为 ⌊m/2⌋。
- 按上述规则扫一遍即可构造方案。m 到 1000000，必须 O(m)。
