题解 P1986 【元旦晚会】

· · 题解

贪心思想

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

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

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

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

代码打出来还是很容易的

#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 序列 这是道蓝题

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

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

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

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