题解：P10934 西瓜种植

大宋宝宝 · 2024-09-16 20:51:53 · 题解

思路

可以贪心的想：如果想要种的瓜最少，一定是让重叠的最多，那么我们就可以将数组按照右端点从小到大排序，然后种树时从后往前枚举，只要这个点之前没有种过瓜，就在这个点种瓜，这样重叠的瓜的数量就最多，也就是种的瓜的数量最少。详见代码注释。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
// ans 表示总数 
bool b[5001];
// b 数组用来标记哪些点种过树了 
struct shu {
    int b,e,t;
} a[5001];
bool cmp(shu a1,shu a2) {
    return a1.e<a2.e;
}
//按照右端点从小到大排序的函数 
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        cin>>a[i].b>>a[i].e>>a[i].t;
        //输入 
    }
    sort(a+1,a+m+1,cmp);
    //按照右端点从小到大排序 
    for(int i=1; i<=m; i++) {
        for(int j=a[i].b; j<=a[i].e; j++) {
            if(b[j]&&a[i].t>0) a[i].t--;
            //如果和之前种的有重合，就让现在要种的次数减一 
            //前提是种的次数不能减到 0 以下了，不然会 RE 
        }
        int now=a[i].e;
        // now 表示当前要种的树的位置 
        while(a[i].t--) {
            while(b[now]) now--;
            //如果当前位置已经种过树了 
            //就考虑前一个位置 
            //直到当前位置没有种过树为止 
            b[now]=1;
            //在当前位置种一棵树，然后标记此处种了树 
            ans++;
            //总数加一 
        }
    }
    cout<<ans;
    //输出总数 
    return 0;
}

AC记录