洛谷P1250种树（贪心）

题目描述

一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。

写一个程序完成以下工作：

输入输出格式

输入格式：

第一行包含数据N，区域的个数(0<N≤30000)；

第二行包含H，房子的数目(0<H≤5000)；

下面的H行描述居民们的需要：B E T，0<B≤E≤30000，T≤E-B+1。

输出格式：

输出文件只有一行写有树的数目

输入输出样例

输入样例#1：

输出样例#1：

/*

首先按右端点从小到大排序

从最右边开始种树

正解是差分约束，不会！

*/

#include<cstdio>

#include<iostream>

using namespace std;

int m,n,zh[]={},a[],b[],sz[];

void qsort(int s1,int s2) //手写快排

{

    int mid1=b[(s1+s2)/];

    int i=s1,j=s2,t;

    while (i<=j)

    {

        while (b[i]<mid1) i++;

        while (b[j]>mid1) j--;

        if (i<=j)

        {

            t=b[i];b[i]=b[j];b[j]=t;

            t=a[i];a[i]=a[j];a[j]=t;

            t=sz[i];sz[i]=sz[j];sz[j]=t;

            i++;j--;

        }

    }

    if (i<s2) qsort(i,s2);

    if (j>s1) qsort(s1,j);

}

int main()

{

    int zs=,i,j,o;

    cin>>m;

    cin>>n;

    for (i=;i<=n;i++)

      cin>>a[i]>>b[i]>>sz[i];

    qsort(,n);

    for (i=;i<=n;i++)

    {

        int js=;

        for (j=b[i];j>=a[i];j--)

          if (zh[j]==) js++;   //计算区域内种了几棵树。

        if (js<sz[i])   //如果不够

        {

            o=sz[i]-js;  //求出还要种几棵树。

            zs+=o;  //累加树的棵数不解释

            for (j=b[i];j>=a[i];j--)  //从最右边开始种树

              if (zh[j]==) { if (o==) break;zh[j]=;o--;  //当然注意要在没有树的地方才能种树。

              }

        }

    }

    cout<<zs;  //最后输出最少种多少棵树

    return ;

}

巴特西

洛谷P1250种树（贪心）

题目描述

输入输出格式

输入输出样例

最新文章

热门文章