本文主要是介绍MT2076 小码哥处理订单，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：
使用二分：题目中隐含条件：如果不满足，需要找到第一个不满足的订单。
二分法需要满足单调性or有一个界线使前后两部分性质相反。这里的”界线“为：是否满足条件。假设第i天无法满足，则后面的所有天都无法满足，前面的天都可以满足。即此时的i为要求的答案
代码：
1.二分+差分
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int r[N];
int d[N], s[N], t[N];
int ans;
int a[N], b[N]; // 差分和前缀和数组bool check(int num) // 判断此订单是否满足条件
{memset(a, 0, sizeof(a));for (int i = 1; i <= num; i++)//遍历订单{ // 差分a[s[i]] += d[i];a[t[i] + 1] -= d[i];}for (int i = 1; i <= n; i++)//遍历天数 { // 前缀和b[i] = b[i - 1] + a[i];if (b[i] > r[i]){return true;}}return false;
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> r[i];}for (int i = 1; i <= m; i++){cin >> d[i] >> s[i] >> t[i];}int l = 1, r1 = m; // 搜索空间：1-mif (!check(m)){cout << 0;return 0;}int mid;while (l <= r1){mid = (l + r1) / 2;if (check(mid)){ans = mid;r1 = mid - 1;}else{l = mid + 1;}}cout << -1 << endl;cout << ans;return 0;
}
2.暴力
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int r[N];
int d, s, t;
int ans;
int day[N];
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> r[i];}for (int i = 1; i <= m; i++){cin >> d >> s >> t;if (ans == 0){for (int j = s; j <= t; j++) // 遍历每天{day[j] += d;if (r[j] < day[j]){ans = i;break;}}}}if (ans == 0){cout << 0;}else{cout << -1 << endl;cout << ans;}
}
这篇关于MT2076 小码哥处理订单的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
