1、上学闹钟

题目描述：

题目从牛客网上找

小明定了n个闹钟，他只能在闹钟响起时出发去学校，每个闹钟时间分别为hi点mi分，小明家到学校要x分钟，学校上课时间a点b分 （0-24 小时，0-59分钟），求他最晚几点起

输入：

3 //定了几个闹钟
5 0 //第1个闹钟的小时数和分钟数
6 0 //第2个闹钟的小时数和分钟数
7 0 //第3个闹钟的小时数和分钟数
59 //到学校要多少分钟
6 59 //上课的小时数和分钟数

输出：

6 0 //最晚的起床时间

思路:

可以把时间都换成分钟，然后从大到小排序，找到第一个能够到达的闹钟从而找到起床时间。

// 这是别的人ac代码
struct Time
{
    int h;
    int m;
    friend bool operator < (Time a, TIme b){
        if(a.h == b.h){
            return a.m > b.m;
        }
        return a.h > b.h;
    }
}
int main()
{
	int n, x, a, b, rest;
	cin >> n;
	Time* time = (Time*)malloc(n * sizeof(Time));
	for (int i = 0; i < n; i++)
	{
		cin >> time[i].h >> time[i].m;
	}
	sort(time, time + n);
	cin >> x;
	cin >> a >> b;
	for (int i = 0; i < n; i++)
	{
		rest = 0;
		if (time[i].h < a || time[i].h == a && time[i].m < b)
		{
			rest = (a - time[i].h) * 60 + b - time[i].m;
			if (rest >= x)
			{
				cout << time[i].h << ' ' << time[i].m << endl;
				break;
			}
		}
	}
	return 0;
}

2. 加密通信 O(n)

小明和小红采用密码加密通信，每次通信有固定的明文长度n和加密次数k。

比如：密码二进制明文是1001010，加密次数是4，则每次将密文右移1位与明文做异或操作 ，总共位移3次（k=4, 所以 k - 1 = 3）

输入：

7 4 // n k
1110100110 //密文

输出：
1001010 //明文

解释：

1001010—
-1001010–
–1001010-
—1001010
加密次数为4，故对于明文右移4-1=3轮，每轮与当前密文进行一次异或，故 1001010对应密文为 1110100110

思路

前置知识：异或的数字异或一次就会变成原数字，举例，101 和011 异或成110，110和011 异或之后变成原来数字101。

首先密文和明文 第1位是一样的，看一下上方样例里的解释就懂了。

然后考虑 第2到k-1位，可以发现这一段的每一位都是由 前一位密文的 异或 结果 再 与当前位明文异或得到的。

接下来考虑 第k到n-1位，观察规律可以发现这一段的每一位都是由 前一位密文与第i-k位明文异或得到的结果再与当前位明文异或得到的。

如何消除异或影响大家应该都能理解，因此只要把参与异或的部分再与密文异或一下即可得到明文。

int main() {
	int n, k, tmp;
	string s,ans="";
	cin >> n >> k;
	cin >> s;
	ans += s[0];
	for (int i = 1; i < k; i++)
	{
		tmp = (int)(s[i] - '0') ^ (int)(s[i - 1] - '0');
		ans += tmp + '0';
	}
	for (int i = k; i < n; i++)
	{
		ans += (int)(s[i] - '0') ^ (int)(s[i - 1] - '0') ^ (int)(ans[i - k] - '0') + '0';
	}
	cout << ans;
	return 0;
}

3.发工资O(n)/O(nlogn)

王大锤要给员工发工资，员工从左到右坐成一排，每个员工知道彼此的资历，每个员工只知道自己左右员工的工资，如果某员工比左边或右边的人资历老，那他一定比这个人工资高100元，每个人最低工资100元，求王大锤最低给多少工资。

样例

输入：

4 //几个员工
3 9 2 7 //员工顺序以及对应的资历

输出：
600 //100 元，20 0元，100元，200元

6
1 2 3 4 5 6
2100 //100，200，300，400，500，600

5
1 1 1 1 1

500 //100，100，100，100，100

8
1 2 3 4 3 2 3 4

1800 //100 200 300 400 200 100 200 300
8
3 4 3 4 3 4 3 4

1200 //100 200 100 200 100 200 100 200
5
1 2 3 4 1

1100 //100 200 300 400 500

思路1 （时间复杂度为o（n））

广度优先搜索，可以把员工序列看作一棵 多根树，每个 工资最低的员工就是根节点，一个员工的工资其实就是他在 多根树里的深度，

首先在输入的时候找到比左右资历都年轻的员工入队，每次从队列pop一个员工，然后判断该员工的最小工资，然后判断左右员工是否可以入队，直到所有员工出队

int main() {
	int n, now;
	long long ans = 0;
	cin >> n;
	if (n == 0)
	{
		cout << 0 << endl;
		return 0;
	}
	vector<int> epy(n, 0), depth(n, 0);
	queue<int> sal;
	for (int i = 0; i < n; i++)
	{
		cin >> epy[i];
		if (i > 1 && epy[i - 1] <= epy[i - 2] && epy[i - 1] <= epy[i])
		{
			depth[i - 1] = 1;
			sal.push(i - 1);
		}
	}
	if (epy[0] <= epy[1])
	{
		depth[0] = 1;
		sal.push(0);
	}
	if (epy[n - 1] <= epy[n - 2])
	{
		depth[n - 1] = 1;
		sal.push(n - 1);
	}
	while (!sal.empty())
	{
		now = sal.front();
		int left = (now > 0 && epy[now-1] < epy[now]) ? depth[now - 1] : 0;
		int right = (now < n - 1 && epy[now + 1] < epy[now]) ? depth[now + 1] : 0;
		sal.pop();
		if (depth[now] == 0)
		{
			depth[now] = max(left, right) + 1;
		}
		//left
		if (now > 0 && depth[now - 1] == 0 && (now == 1 || epy[now - 2] > epy[now - 1] || depth[now - 2] > 0))
		{
			sal.push(now - 1);
		}
		//right
		if (now < n - 1 && (depth[now + 1] == 0) && (now == n - 2 || epy[now + 2] > epy[now + 1] || depth[now + 2] > 0))
		{
			sal.push(now + 1);
		}
	}
	for (auto salary : depth) {
		ans += salary;
	}
	cout << ans * 100 << endl;
}

思考2 （时间复杂度olog（n））

用贪心思路，先全部输入结构体内，然后按照分数大小排序，从最小的开始如果旁边有没有分数那就是100，如果有就比有分数最高的多100.