考完一堆期中之后终于想起自己还有一个blog QAQ…
1011. 经典的猜数游戏
一道比较基础的交互题，你可以理解成：机器想了一个数字，你要靠“输出”的方式告诉机器你猜的数字是什么
然后，机器说一个词big/small/equal来告诉你猜得对不对，你需要再靠“输入”的方式从机器那里获得这个反馈
总的流程就是：你先猜一个数（输出，printf/cout）——机器收到，告诉你猜得对不对——你靠输入得到这个反馈（scanf/cin）——调整你猜的数字
那么要怎么猜呢？
如果你熟悉二分算法，那就直接写一个二分上去就可以了，如果不太理解可以看看下面的解释：
我们假设，现在我想了1-100之间的数字，对于你的每次猜测，我都会告诉你“大了/小了/猜对了”
假如你不知道，你可能会先随便猜一个50，这时候我会告诉你大了，然后你肯定要猜更小的数字
这时候，你可以选择猜49，48……以此类推，但如果我想的是1呢？你得问整整50遍……
更高效的方法是，每次猜当前剩下的可能的区间的中间值（下取整）
比方说刚才你猜50，我说大了，显然可能的数字只会在1-49之间，你猜中间值25；
如果我又说大了，可能值只会在1-24之间，你猜12；如果说小了，可能值则在26-49之间，你猜37
这样的好处是，无论在什么情况（即使你是非酋），你的总猜测次数是理论最小的
参考代码如下，注意每次得到big/small的反馈后mid区间的调整
#include <bits/stdc++.h>
using namespace std;
int main() {
int l = -1e9;
int r = 1e9;
string response;
while (true) {
int mid = (l + r) >> 1;
cout << mid << endl;
cin >> response;
if (response == "equal") {
return 0;
} else if (response == "big") {
r = mid - 1;
} else {
l = mid + 1;
}
}
return 0;
}1012. 环形队列
循环队列板题，直接照搬ppt上代码即可
注意ppt上的循环队列实现留出了一个空位置，也就是相当于要把队列长度+1
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 100002
int q[MAX_N];
int front = 0,rear = 0;
void enqueue(int x) {
if ((rear + 1) % MAX_N == front) {
return;
}
q[rear] = x;
rear = (rear + 1) % MAX_N;
}
void dequeue(void) {
if (front == rear) {
cout << -1 << endl;
return;
}
int e = q[front];
front = (front + 1) % MAX_N;
cout << e << endl;
}
int main() {
int t,x;
string ope;
cin >> t;
while(t--) {
cin >> ope;
if (ope == "enqueue") {
cin >> x;
enqueue(x);
} else {
dequeue();
}
}
return 0;
}1013. 医疗调度系统
一道hard题，可能很多人刚刚看到这一题的时候会觉得不难，以为直接把全国家的人口存在一个数组里，然后按照题意模拟就可以
需要注意的是，题目提到1 <= P <= 1000000000，无论是直接存成数组（MLE）或者循环（TLE）都不行
好消息是，进程命令的数量很小1 <= C <= 1000，所以我们可以维护一个长度为min(P,C)的队列，这样长度最大也就是1000，可以使用O(n^2)的算法
具体怎么做呢？N接收下一个公民：队列出队首E x加速公民：遍历队列，如果队列中有x，就把x从原来的位置上“揪出来”到队首，后面的人填上去；如果没有，则直接在队首插入x
时间复杂度O(N^2)
#include <bits/stdc++.h>
using namespace std;
deque<int> q;
int main() {
int p,c;
int cas = 0;
while(cin >> p >> c) {
q.clear();
if (p == 0 && c == 0) {
break;
}
printf("Case %d:\n",cas);
cas++;
int len = min(p,c);
for (int i = 1;i <= len;i++) {
q.push_back(i);
}
char ope;
int x;
while(c--) {
cin >> ope;
if (ope == 'N') {
int tmp = q.front();
cout << tmp << endl;
q.pop_front();
q.push_back(tmp);
} else {
cin >> x;
for (int i = 0;i < q.size();i++) {
if (q[i] == x) {
q.erase(q.begin() + i);
break;
}
}
q.push_front(x);
}
}
}
return 0;
}PS：金牌助教在课上提出了一个双指针做法，他的想法是只用维护一个变量tmp作为“正常排队的人”，一个队列作为插队队列，如果插队队列非空，优先出队，否则输出tmp，并且tmp++
但是坏消息是这个想法被打acm的同学华丽丽地hack掉了……（乐），以下是打acm的同学构造的一组数据：
3 5
E 2
N
N
N
N
正确输出应该是2 1 3 2，但是用学长的这种方法会得到2 1 2 3的错误答案，也就是说这种做法不能很好地处理“插队”的情况，如果一个人被优先服务过了，他本来应该被从正常排队的位置丢到队伍最后，但是学长的方法还是没办法处理这个问题
1014. 循环打印
因为涉及到频繁的结点删除，所以使用单链表，时间复杂度O(nk)
以下做法使用了结构体表示结点
需要注意的是，题目中“以k为步长打印”的意思相当于是从当前的数开始数k次，删掉第k个数，样例中从5开始，数5，6，7三个数字，所以第一个要删除的数是7
具体写代码的话，我的方法是维护pre和now两个结点，now初始值为i，pre初始值为i-1（now不等于1）或n（now等于1）
每次先移动k-1次，输出当前的数（比如说样例，从5开始先移动两次，i从5到7，这个时候先输出now），再“删除”当前结点（将nodes[pre].nex改成nodes[now].nex，也就是6的后继变成了8），最后再移动一次now（now从7到8）
#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
int nex;
};
int main() {
int n,i,k;
cin >> n >> i >> k;
node nodes[103];
for (int j = 1;j <= n-1;j++) {
nodes[j].data = j;
nodes[j].nex = j+1;
}
nodes[n].nex = 1;
int pre = i == 1?n:i-1,now = i;
while (n--) {
for (int step = 0;step < k-1;step++) {
pre = now;
now = nodes[now].nex;
}
cout << now << " ";
nodes[pre].nex = nodes[now].nex;
now = nodes[now].nex;
}
return 0;
}也可以使用数组模拟链表，思路是数组nodes的下标i代表当前数字为i，nodes[i]则代表数字为i的结点下一个数为nodes[i]
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,i,k;
cin >> n >> i >> k;
int nodes[105];
for (int j = 1;j <= n-1;j++) {
nodes[j] = j+1;
}
nodes[n] = 1;
int pre = i == 1?n:i-1;
int now = i;
while (n--) {
for (int step = 0;step < k-1;step++) {
pre = now;
now = nodes[now];
}
cout << now << " ";
nodes[pre] = nodes[now];
now = nodes[now];
}
return 0;
}1015. 题库整理
一道比较有意思的题目
需要完成的操作：
- 1 给定题目难度并且入库题目
- 2 最后入库的题目出库
- 3 输出当前题库内最难题目的难度
看到“最后入库的题目出库”，肯定是先想到使用栈作为数据结构，但是输出最难题目的难度应该怎么做呢？
我们可以换一种思路，维护一个栈，但是每次放入的不是题目的难度，而是当前所有题目最大的难度，或者说，假设刚才题库里所有题目的最大难度是maxx，每次收到一本新书，你需要比较maxx和新书的难度，然后将较大的那个值压入栈
然后，操作2就是正常弹出栈顶，操作3是获取栈顶的值但不弹出
我觉得可以这么理解：越早入库的题目，肯定越晚出库，而对于先后入库的题目A和B，假如A的难度大于B，那么在弹出A之前，要求输出当前题库内最难题目的难度时其实一直都是A的难度
所以说，栈的内容只要是当前所有题目最大的难度就可以
#include <bits/stdc++.h>
using namespace std;
int maxx[200005] = {0};
int main() {
int n;
scanf("%d",&n);
int ope,x;
int point = 0;
while (n--) {
scanf("%d",&ope);
if (ope == 0) {
scanf("%d",&x);
point++;
maxx[point] = x > maxx[point-1] ? x : maxx[point-1];
}else if(ope == 1) {
if (point > 0){
point--;
}
}else {
printf("%d\n",maxx[point]);
}
}
return 0;
}