自动搬运

查看原文

来自洛谷，原作者为

	Ayanami 这个家伙很菜，什么也没有留下

搬运于2025-08-24 21:32:39，当前版本为作者最后更新于2019-11-06 11:26:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

贪心思想

对于每个声部按照右端点从小到大排序

然后从每个右端点往左发话筒直到该声部话筒数量足够

（每种颜色表示一个声部）

可以证明这样能使重复部分的话筒最多，因为按右端点排序后每个声部与它之后的声部的重复（如果有）一定会从最右边开始

代码打出来还是很容易的

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,ans=0,s,a;
struct node
{
	int l,r,t;
}
x[10001];//结构体
bool z[30001]={0};//记录该位置是否有话筒
bool cmp(node x,node y)
{
	return x.r<y.r;//按右端点排序
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
	    scanf("%d%d%d",&x[i].l,&x[i].r,&x[i].t);
	}
	sort(x+1,x+m+1,cmp);//排序
	for(int i=1;i<=m;i++)
	{
		a=0;//计数
		//先扫一遍统计该声部现有话筒个数
		for(int j=x[i].l;j<=x[i].r;j++)
		{
			if(z[j])
			{
			    a++;
			}
		}
		//从尾巴开始放
		for(int j=x[i].r;j>=x[i].l;j--)
		{
			//够了就退出
			if(a>=x[i].t)
			{
				break;
			}
			//这里没有话筒就放一个
			if(!z[j])
			{
				a++;
				ans++;
				z[j]=1;
			}
		}
	}
	printf("%d",ans);
}

P.S 论这题的颜色

P1250 种树 这是道黄题

P1645 序列 这是道蓝题

做法 完 · 全 · 一 · 致 三倍经验

众所周知黄色和蓝色混起来是绿色所以这是道绿题

又众所周知你谷上绿题难度在黄蓝之间所以取平均值这题还是绿的

大雾所以这题为什么是蓝的