题解
OJ 1-10 题解
T1
提供两个解法，分别是用队列模拟和用数组模拟（记录入队时间和状态）：
// queue队列模拟
#include <bits/stdc++.h>
#define N 15
#define M 1005
#define ll long long
using namespace std;
int n, m;
int T[N], W[N];
int t[M], w[M];
struct tmp
{
int i;
int enterTime;
};
queue <tmp> trans[N]; // 传送带队列
queue <tmp> wait[N]; // 等待区队列
ll sum[N];
int main()
{
scanf("%d %d", &n, &m);
int minW = 0;
for (int i = 1; i <= n; i++) {
scanf("%d %d", &T[i], &W[i]);
if (!minW || minW > W[i]) minW = W[i];
}
int flag = 1;
for (int i = 1; i <= m; i++) {
scanf("%d %d", &t[i], &w[i]);
if (w[i] > minW) flag = 0;
}
if (!flag) {
printf("invalid\n");
return 0;
}
int Time = 0;
int l = 1;
int finished = 0;
while (++Time) {
for (int i = 2 * n; i; i--) { // 从后往前更新，更新顺序为传送带->等待区->传送带->等待区->...
if ((i & 1) == 0) { // trans 传送带处理
int id = i / 2;
while (!trans[id].empty() && Time - trans[id].front().enterTime >= T[id]) {
tmp now = trans[id].front();
trans[id].pop();
sum[id] -= w[now.i];
if (id < n) {
if (sum[id + 1] + w[now.i] <= (ll)W[id + 1] && wait[id + 1].empty()) {
// 等待区为空才能直接进入下一个传送带，否则需要等之前进入传送带的物品
trans[id + 1].push({now.i, Time});
sum[id + 1] += w[now.i];
}
else {
wait[id + 1].push({now.i, Time});
}
}
else finished++;
}
}
else { // wait 等待队列处理
int id = i / 2 + 1;
while (!wait[id].empty() && sum[id] + w[wait[id].front().i] <= (ll)W[id]) {
tmp now = wait[id].front();
wait[id].pop();
trans[id].push({now.i, Time});
sum[id] += w[now.i];
}
}
}
while (l <= m && t[l] <= Time) { // 新物品进入整个系统
if (w[l] + sum[1] <= W[1] && wait[1].empty()) {
trans[1].push({l, Time});
sum[1] += w[l];
}
else {
wait[1].push({l, Time});
}
l++;
}
if (finished == m) break;
}
printf("%d\n", Time);
return 0;
}
// 数组模拟
#include<cstdio>
long long w[1010], mxw[15], miw = 10000000000ll, weightOnBelt[15];
int n, m;
int head[15], tail[15], leavetime[1010], passtime[15], ans;
int main()
{
scanf("%d%d", &n, &m);
head[0] = m;
tail[0] = 1;
for(int i = 1; i <= n; i++)
{
scanf("%d%lld", &passtime[i], &mxw[i]);
tail[i] = 1;
miw = miw < mxw[i] ? miw : mxw[i];
}
for(int i = 1; i <= m; i++)
{
scanf("%d%lld", &leavetime[i], &w[i]);
if(w[i] > miw)
{
printf("invalid\n");
return 0;
}
}
while(tail[n] < m+1)
{
int dt = 2100000; // 设定一个足够大的值
for(int i = 0; i <= n; i++)
{
if(tail[i] <= head[i])
dt = dt < leavetime[tail[i]] ? dt : leavetime[tail[i]];
}
ans += dt;
for(int i = 1; i <= m; i++)
leavetime[i] -= dt;
for(int i = 0; i <= n; i++)
{
while(leavetime[tail[i]] == 0 && tail[i] <= head[i])
{
weightOnBelt[i] -= w[tail[i]];
tail[i]++;
}
}
for(int i = 1; i <= n; i++)
{
while(head[i] < m && leavetime[head[i]+1] <= 0 && weightOnBelt[i] + w[head[i]+1] <= mxw[i])
{
head[i]++;
weightOnBelt[i] += w[head[i]];
leavetime[head[i]] = passtime[i];
}
}
}
printf("%d\n", ans);
return 0;
}
可以看出，数组模拟的代码明显要简单不少。用数组模拟简单数据结构（栈、队列、链表等）是较简便的方法。
T2
#include <cstdio>
#include <stack>
#define _N 100010
int n;
std::stack<int> s1, s2;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int opt, x;
scanf("%d", &opt);
switch(opt) {
case 1:
if (s1.empty()) {
puts("invalid option 1");
} else {
s2.push(s1.top());
s1.pop();
}
break;
case 2:
if (s2.empty()) {
puts("invalid option 2");
} else {
s1.push(s2.top());
s2.pop();
}
break;
case 3:
scanf("%d", &x);
s1.push(x);
break;
case 4:
if (s1.empty()) {
puts("invalid option 4");
} else {
s1.pop();
}
break;
case 5:
if (s1.empty()) {
puts("invalid option 5");
} else {
printf("%d\n", s1.top());
}
break;
case 6:
printf("%d\n", (int)s1.size());
break;
}
}
return 0;
}
双栈模拟即可。
T3
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 107, INF = 0x3f3f3f3f;
char s[107], t[107];
ll len[107];
int n, m;
char solve(int day, ll k){
if(day == 1) return s[k];
if(day == 2) return t[k];
assert(k <= len[day]);
if(k <= len[day - 2])return solve(day - 2, k);
else return solve(day - 1, k - len[day - 2]);
}
int main(){
scanf("%s", s + 1); // 表示从s字符数组下标1的位置开始读入
scanf("%s", t + 1);
n = strlen(s + 1);
m = strlen(t + 1);
len[1] = n, len[2] = m;
for(int i = 3; i <= 35; i++)
len[i] = len[i - 1] + len[i - 2];
int Q;
scanf("%d", &Q);
while(Q--) {
int day; ll k;
scanf("%d%lld", &day, &k);
for(ll i = k; i <= min(k + 9, len[day]); i++)
printf("%c", solve(day, i));
putchar('\n');
}
return 0;
}
题目中已经推荐本题对于10个连续的字母，当作10个分开的字母各自计算并输出。考虑如果将10个字母递归地放入计算函数中一并输出（即将递归的solve增加一个参数表示“想要输出的长度”），那么想要计算的段很有可能在某时某刻“跨越”了组成当前段的两个子段，那么就需要对于两个分别的solve函数截取不同的“字母长度”参数，计算起来容易出错。