CF69B Bets 题解

题意简述

给定两个整数 $n$，$m$。分别代表有 $n$ 条赛道，$m$ 个运动员。

接下来 $m$ 行，每行 4 个整数 $l_i , r_i , t_i , c_i$。分别代表这位运动员从 $l_i$ 滑到 $r_i$，每一段赛道花费的时间为 $t_i$，这个赌注值 $c_i$ 卢布。

问最大收益是多少。

解题思路

建两个数组 $maxx , mon$，分别表示这一个赛道的最短时间和这个最短时间所对应的赌注的收益。

每次输入，枚举 $l_i$ 到 $r_i$。如果这位选手的时间大于 $maxx_i$，就更新这个 $maxx_i$ 和 $mon_i$。

最后从 $1$ 到 $n$ 枚举一遍，累加 $mon_i$ 即可。

代码实现

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,ans;
int maxx[1000005],mon[1000005];
int main() {
	memset(maxx,inf,sizeof(maxx));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) {
		int l,r,t,c; scanf("%d%d%d%d",&l,&r,&t,&c);
		for(int j=l;j<=r;j++) {
			if(t<maxx[j]) maxx[j]=t,mon[j]=c;
		}
	}
	for(int i=1;i<=n;i++) ans+=mon[i];
	printf("%d",ans);
	return 0;
}
//code by TheCedar