信息学奥赛一本通T1423-种树

解题思路:

代码的思路是首先按照结束位置end对s数组进行从小到大的排序，然后遍历s数组中的每个元素。对于每个元素，首先计算数组a中在结束位置end到开始位置start之间已经被覆盖的位置数sum。如果sum大于等于需要被覆盖的次数t，则跳过该元素，继续遍历下一个元素。否则，从结束位置end开始向起始位置start遍历数组a，未被覆盖的位置设为被覆盖，并更新sum和被覆盖位置的计数器ant。当sum等于t时停止遍历。

最后输出被覆盖的位置数ant。

注意事项:

参考代码:

#include<iostream>

#include<algorithm>

using namespace std;

struct node

{

    int start,end,t;

}s[30000];

int a[30000]={0};

bool cmp(node &a,node &b){return a.end<b.end;}

int main()

{

    int ant=0;

    int n,h; cin>>n>>h;

    for(int i=1;i<=h;i++)   cin>>s[i].start>>s[i].end>>s[i].t;

    sort(s+1,s+1+h,cmp);

    for(int i=1;i<=h;i++)

    {

        int sum=0;

        for(int j=s[i].end;j>=s[i].start;j--)

        {

            if(a[j]==1) sum++;

        }

        if(sum>=s[i].t) continue;       //满足，则下一个i

        else                            //不满足，就补起来

        {

            for(int j=s[i].end;j>=s[i].start;j--)

            {

                if(a[j]!=1)

                {

                    a[j]=1;

                    sum++;

                    ant++;

                }

                if(sum==s[i].t) break;

            }

        }

    }

    cout<<ant<<endl;

    return 0;

}