考试总结

I n d e x ： Index： Index：

今天全真考试没啥可说一开始把T1想难了花了将近四十分钟解决，

然后发现C++只要写 a l g o r i t h m algorithm algorithm或者万能头就要打开函数库，

哇~我直接瓦开然后又重新下了C++然后才开始继续写T2

还好今天脑袋没有抽，居然把T3想出来了。。。。

简单讲一下T1和T2，重点说一下T3 GM说思维很强

T1 数你太美

题目新颖。。。让我想到某菜

这道题意思就是在两个序列里面分别找到一个最小的，然后进行合体合并，

然后变成一个更小的，如果加起来的那个数等于2，直接输出，之后就直接按照题意写

即可

---

T2 逃亡

这道题，我觉得才是签到题，前面那个真的一不注意就会写错

这道题题意都不用理解，就是在一个平面直角坐标系里找出x，y的最短路，然后sum加起来

代码

for(int i = 1;i <= k;i ++){
        x  = read(), y = read();
        temp1 = min(x, n - x);
        temp2 = min(y, m - y);
        sum += min(temp1 , temp2);
}

---

T3 数数字

这道题的题意很好懂，但是最开始我确实没有思路。

然后又读。。。然后发现一个关键点：

第 i 个蒟蒻会告诉你他看到了 ai 种数字(定义两个数字不同种当且仅当它们的值不同)
但是由于蒟蒻太弱了，可能会报错数据，NTF 需要核实是否有一种情况使所有蒟 蒻说的话都正确。(可能情况不唯一)

那么不难看出总共有 a i a_i ai​种卡片，每个蒟蒻看到的种数是 a i a_i ai​ - 1（唯一），不然就是 a i a_i ai​(不唯一)

由此可以推出两个数如果相差了2及其以上就已经不用管了：因为无法平均的。

继续按这个思路推，当 m a x max max和 m i n min min不同时，就只有两种情况，max = min或max - 1 = min。

如果每只蒟蒻看到的卡片的总数是 a i a_ i ai​ - 1，此时无解。然后 a i a_i ai​ = n的时候

由于不存在孤独的蒟蒻，所以 a i a_i ai​ 至多为n / 2。最后当 m a x − 1 = m i n max - 1 = min max−1=min的时候

此时我们可以统计孤独的蒟蒻的个数有 o o o 个 类似上面的推论， 数值总数至少为 o + 1 o + 1 o+1

最多就有 ( n − o ) / 2 + o (n - o) / 2 + o (n−o)/2+o，所以得到这个

o + 1 <= maxn && maxn <= (n - o) / 2 + o

代码

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int maxn = 1000000;
int T, n;
int a[maxn + 5];
int o;

inline int read() {
    char c = getchar();
    int x = 0, f = 1;
    while (c < 48 || c > 57) {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57) {
        x = x * 10 + c - 48;
        c = getchar();
    }
    return x * f;
}

int work() {
	T = read();
	while(T --) {
		n = read();
		int maxn = false;
		int minn = 0x3f3f3f3f;
		o = 0;
		
		for(int i = 1;i <= n;i ++) {
			a[i] = read();
			if(maxn < a[i]) maxn = a[i];
			if(minn > a[i]) minn = a[i];
		}
		
		for(int i = 1;i <= n;i ++) {
			if(a[i] == minn) o ++;
		}
		
		if(maxn - minn > 1) {
			printf("no\n");
			continue;
		}
		
		if(maxn - minn == 1) {
			if(o + 1 <= maxn && maxn <= (n - o) / 2 + o) {
				printf("yes\n");
			}
			else {
				printf("no\n");
			}
		}
		
		if(maxn == minn) {
			if(maxn  * 2 <= n || maxn == n - 1) {
				printf("yes\n");
				continue;
			}
			printf("no\n");
			continue;
		}
	}
}

int main(){
	work();
	return 0;
}