网站建设前十名,网站建设 招标书,怎样免费制作网站,html5制作网站模板目录 1. 班级活动1. 问题描述2. 输入格式3. 输出格式4. 样例输入5. 样例输出6. 样例说明7. 评测用例规模与约定8. 原题链接 2. 解题思路3. AC_Code 1. 班级活动
前置知识点#xff1a;思维#xff0c;分类讨论
1. 问题描述
小明的老师准备组织一次班级活动。班上一共有 n… 目录 1. 班级活动1. 问题描述2. 输入格式3. 输出格式4. 样例输入5. 样例输出6. 样例说明7. 评测用例规模与约定8. 原题链接 2. 解题思路3. AC_Code 1. 班级活动
前置知识点思维分类讨论
1. 问题描述
小明的老师准备组织一次班级活动。班上一共有 n n n 名 ( n n n 为偶数) 同学老师想把所有的同学进行分组每两名同学一组。为了公平老师给每名同学随机分配了一个 n n n 以内的正整数作为 id \text{id} id第 i i i 名同学的 id \text{id} id 为 a i a_i ai。
老师希望通过更改若干名同学的 id \text{id} id 使得对于任意一名同学 i i i有且仅有另一名同学 j j j 的 id \text{id} id 与其相同 ( a i a j a_i a_j aiaj)。请问老师最少需要更改多少名同学的 id \text{id} id
2. 输入格式
输入共 2 2 2 行。
第一行为一个正整数 n n n。
第二行为 n n n 个由空格隔开的整数 a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1,a2,...,an。
3. 输出格式
输出共 1 1 1 行一个整数。
4. 样例输入
4
1 2 2 35. 样例输出
16. 样例说明
仅需要把 a 1 a_1 a1 改为 3 3 3 或者把 a 3 a_3 a3 改为 1 1 1 即可。
7. 评测用例规模与约定
对于 20 % 20\% 20% 的数据保证 n ≤ 1 0 3 n ≤ 10^3 n≤103。
对于 100 % 100\% 100% 的数据保证 n ≤ 1 0 5 n ≤ 10^5 n≤105。
8. 原题链接
班级活动
2. 解题思路
首先明确一点假设某个 id \text{id} id 的同学数量为 x ( x 2 ) x(x2) x(x2)因为题目要求任意 id \text{id} id 只能有两名同学所以一定会有 x − 2 x-2 x−2 名同学修改自己的 id \text{id} id。我们可以计算出每个 id \text{id} id 需要修改自身的同学数量之和并将这个数量设为 b b b即满足 b ∑ i 1 n max ( 0 , a i − 2 ) b\sum_{i1}^{n}\max(0,a_i-2) bi1∑nmax(0,ai−2) 还有一个特殊群体我们不能忽略就是编号 id \text{id} id 唯一的同学我们设这群同学的数量为 a a a。他们特殊在有可能需要修改自身 id \text{id} id也有可能不需要我们需要进行分类讨论。
当 b ≥ a b \ge a b≥a 时
在这种情况下 id \text{id} id 唯一的 a a a 名同学是不需要修改自身 id \text{id} id 的。我们可以从 b b b 名同学中选出 a a a 名同学修改自身 id \text{id} id 去与 id \text{id} id 唯一的同学对应剩下的 b − a b-a b−a 名同学仍然是需要修改自身 id \text{id} id 的所以答案即是 b b b。
假设有一个 id \text{id} id 集合 A { 1 , 2 , 3 , 4 , 4 , 4 , 4 , 5 , 5 , 5 , 5 , 5 } A \lbrace1,2,3,4,4,4,4,5,5,5,5,5\rbrace A{1,2,3,4,4,4,4,5,5,5,5,5}此时 id \text{id} id 唯一的集合为 { 1 , 2 , 3 } \lbrace1,2,3\rbrace {1,2,3}必须修改的 id \text{id} id 集合为 { 4 , 4 , 5 , 5 , 5 } \lbrace4,4,5,5,5\rbrace {4,4,5,5,5}。我们只需要让后一个集合的 id \text{id} id 分别修改为 { 1 , 2 , 3 , 6 , 6 } \lbrace 1,2,3,6,6\rbrace {1,2,3,6,6} 即可符合要求。
当 b a ba ba 时
在这种情况下部分 id \text{id} id 唯一的 a a a 名同学是需要修改自身 id \text{id} id 的。同样假设有一个 id \text{id} id 集合 A { 1 , 2 , 3 , 4 , 5 , 5 , 5 , 5 , 5 , 5 , 6 , 7 } A\lbrace1,2,3,4,5,5,5,5,5,5,6,7\rbrace A{1,2,3,4,5,5,5,5,5,5,6,7}此时 id \text{id} id 唯一的集合为 { 1 , 2 , 3 , 4 , 6 , 7 } \lbrace1,2,3,4,6,7\rbrace {1,2,3,4,6,7}必须修改的 id \text{id} id 集合为 { 5 , 5 , 5 , 5 } \lbrace5,5,5,5\rbrace {5,5,5,5}。按照同样策略我们让必须修改的 id \text{id} id 集合与 id \text{id} id 唯一的集合对应上即将必须修改的 id \text{id} id 集合变为 { 1 , 2 , 3 , 4 } \lbrace1,2,3,4\rbrace {1,2,3,4}。
但此时仍然发现 id \text{id} id 唯一的集合剩余的两个 id \text{id} id 为 { 6 , 7 } \lbrace6,7\rbrace {6,7}我们需要让他们它们一致所以需要修改其中一个。
假设剩余 4 4 4 个呢那我们需要修改 2 2 2 个。
假设剩余 8 8 8 个呢那我们需要修改 4 4 4 个。
显然结论就是需要修改剩余 id \text{id} id 个数的一半即这种情况下答案是 a − b 2 b \dfrac{a-b}{2}b 2a−bb 小疑问如果 a-b 为奇数怎么办
结论 a − b a-b a−b 一定为偶数。我们可以假设数组已经存在 c c c 对匹配好的 id \text{id} id根据我们对 a , b a,b a,b 的定义显然符合式子 a b 2 × c n ab2\times cn ab2×cn。题目告知我们 n n n 一定为偶数且 2 × c 2 \times c 2×c 也一定为偶数那么 a b ab ab 也一定为偶数即说明 a , b a,b a,b 奇偶性一定相同得证 a − b a-b a−b 一定为偶数。
时间复杂度 O ( n ) O(n) O(n)。
3. AC_Code
C
#include bits/stdc.h
using namespace std;
typedef long long LL;int n;
int main()
{cin n;mapint, int cnt;for (int i 0; i n; i){int x;cin x;cnt[x];}int a 0, b 0;for (auto [x, y] : cnt){if (y 1){a;}else if (y 2){b y - 2;}}if (b a){cout b \n;}else{cout (a - b) / 2 b \n;}return 0;
}
Java
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();MapInteger, Integer cnt new HashMap();for (int i 0; i n; i) {int x sc.nextInt();cnt.put(x, cnt.getOrDefault(x, 0) 1);}int a 0, b 0;for (Map.EntryInteger, Integer entry : cnt.entrySet()) {int y entry.getValue();if (y 1) {a;} else if (y 2) {b y - 2;}}if (b a) {System.out.println(b);} else {System.out.println((a - b) / 2 b);}}
}Python
n int(input())
line list(map(int, input().split()))
cnt {}
for i in range(n):x line[i]if x in cnt:cnt[x] 1else:cnt[x] 1
a 0
b 0
for y in cnt.values():if y 1:a 1elif y 2:b y - 2
if b a:print(b)
else:print((a - b) // 2 b)
