A18828. 经典差分应用题
填空题
较难
知识点
题目描述
经典差分应用题
题目描述
学校有 n 个同学排队，初始所有同学的分数为0。现有 m 次加分操作，每次给第 l 到第 r 个同学每人加 k 分。操作结束后，统计分数大于等于 s 的同学人数。
输入格式
第一行三个整数n, m, s（1≤n,m≤2e5，0≤s≤1e4）
接下来 m 行，每行三个整数 l, r, k（1≤l≤r≤n，1≤k≤100）
输出格式
一个整数，表示分数≥s的同学数量
样例输入
6 3 3
1 2 2
2 4 2
5 6 4样例输出
4参考答案
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200010;
long long d[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, s;
cin >> n >> m >> s;
while(m--)
{
int l, r, k;
cin >> l >> r >> k;
d[l] += k;
d[r+1] -= k;
}
// 还原数组并统计数量
int cnt = 0;
long long score = 0;
for(int i = 1; i <= n; i++)
{
score += d[i];
if(score >= s) cnt++;
}
cout << cnt << endl;
return 0;
}
上一题
下一题