该题涉及到时间轴和不同的商家,如果采用暴力则时间复杂度为O(n方)则会超时
所应该只遍历一者,对另外一者进行优化
C++ 代码
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
const int N = 10e5 + 10;
using namespace std;
int n, m, k, ret, ans;
int book[N];
//减法且差最少为0
int SUB(int sum,int b) {
return max(sum-b, 0);
}
map[HTML_REMOVED]> t_d;
int main() {
cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
t_d[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
//将商家的所有订单按时间排序
sort(t_d[i].begin(), t_d[i].end());
int a = 0, sum = 0, flag = 0;
//遍历每家店的所有订单,每收到一单则减去前面未接单的时间然后再加上2
//需要注意的地方是如果一天出现多单则需要特别进行一个特盼
for (auto it = t_d[i].begin(); it != t_d[i].end(); it++) {
int b = *it;
if(a!=b)
sum = SUB(sum, b - a - 1);
else sum=SUB(sum, b - a);
//判断出入优先级
if (sum <= 3)flag = 0;
sum += 2;
if (sum > 5)flag = 1;
//更新最后接单的日期
a = b;
}
//最后时间也需要判断
sum = SUB(sum, k-a);
if (sum <= 3)flag = 0;
if (flag)ans++;
}
cout << ans << endl;
}
第一次写题解 这个格式不是很完美 大家看看主函数部分就好了,欢迎大家指正