（70分）外卖店优先级
题目 外卖店优先级
思路分析
直接模拟能拿70分 考试时可能就只能到这里了
确实乍一看没找到能优化的点
把订单全都存起来 按时间处理 若某时间某店有订单 就加上订单数*2 若没订单 就--
超过5 加入缓存 变得小于等于3 移除
因为这里卡在了空间上 所以尝试用可变长数组来优化空间
然后emm 痛苦转移
超时了 还是过了7个
白改
正解有点麻烦 懒得看了 这种模拟题大概我就做到这 懒得想后面的了
代码实现
7/10 mle
#include <bits/stdc++.h>
using namespace std;
const int Maxsize = 10010;
unordered_map<int, unordered_map<int, int>> orders;
int priority[Maxsize];
bool inCache[Maxsize];
int N, M, T;
int main() {
cin >> N >> M >> T;
while (M--) {
int ts, id;
cin >> ts >> id;
orders[ts][id]++;
}
for (int i = 1; i <= T; i++) {
for (int j = 1; j <= N; j++) {
if (orders[i][j] > 0)
priority[j] += 2 * orders[i][j];
else if (priority[j] > 0)
priority[j]--;
if (priority[j] > 5)
inCache[j] = true;
else if (priority[j] <= 3)
inCache[j] = false;
}
}
int res = 0;
for (int i = 1; i <= N; i++)
res += inCache[i];
cout << res;
return 0;
}
7/10 tle
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int main() {
int n, m, T;
cin >> n >> m >> T;
vector<int> priority(n+1, 0);
vector<bool> inCache(n+1, false);
unordered_map<int, unordered_map<int, int>> orders;
for (int i = 0; i < m; i++) {
int ts, id;
cin >> ts >> id;
orders[ts][id]++;
}
for (int i = 1; i <= T; i++) {
// 如果在该时刻有订单
if (orders.find(i) != orders.end()) {
// 更新所有在该时刻有订单的店铺的优先级
for (auto &order : orders[i]) {
int id = order.first;
int count = order.second;
priority[id] += 2 * count;
if (priority[id] > 5) {
inCache[id] = true;
} else if (priority[id] <= 3) {
inCache[id] = false;
}
}
}
// 对于在该时刻没有订单的店铺，降低优先级
for (int j = 1; j <= n; j++) {
if (orders[i].find(j) == orders[i].end() && priority[j] > 0) {
priority[j]--;
if (priority[j] <= 3) {
inCache[j] = false;
}
}
}
}
int result = count(inCache.begin() + 1, inCache.end(), true);
cout << result;
return 0;
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n, m, T;
int score[N], last[N];
bool st[N];
PII order[N];
int main()
{
scanf("%d%d%d", &n, &m, &T);
for (int i = 0; i < m; i ++ )
scanf("%d%d", &order[i].x, &order[i].y);
sort(order, order + m);
for (int i = 0; i < m;)
{
int j = i;
while (j < m && order[j] == order[i])
j ++ ;
int t = order[i].x, id = order[i].y, cnt = j - i;
i = j;
score[id] -= t - last[id] - 1;
if (score[id] < 0)
score[id] = 0;
if (score[id] <= 3)
st[id] = false; // 以上处理的是t时刻之前的信息
score[id] += cnt * 2;
if (score[id] > 5)
st[id] = true;
last[id] = t;
}
for (int i = 1; i <= n; i ++ )
if (last[i] < T)
{
score[i] -= T - last[i];
if (score[i] <= 3)
st[i] = false;
}
int res = 0;
for (int i = 1; i <= n; i ++ )
res += st[i];
printf("%d\n", res);
return 0;
}
💬 评论