当前时区为 UTC + 8 小时



发表新帖 回复这个主题  [ 12 篇帖子 ] 
作者 内容
1 楼 
 文章标题 : 一条c++题目,请问怎么设计算法
帖子发表于 : 2009-08-18 14:54 
头像

注册: 2009-03-19 8:39
帖子: 185
送出感谢: 0 次
接收感谢: 0 次
引用:
问题描述
某校东侧长度为L的街道一侧有一排树,每两棵相邻的树之间间隔1米,这些树的位置从南到北依次标记为0,1,2,…,L。在树的一侧的一些区域要用来修地铁站,工作人员为图方便,在一些地段标上要修地铁站的标记,即从南到北陆续在需要影响的一段区域插上起始位置与终止位置的标牌,这些区域中的树是要移除的。
您的任务是计算将这些树移除后这段街道还有多少棵树。

输入
输入有多组测试数据,每组有若干行。每组的第一行是2个整数L、M(1£L£10000,1£M£100),其中L表示这一段街道的长度,M表示区域的数目。接下来有M行,每行有2个不同的整数,用空格隔开,表示一个区域的起始位置与终止位置。

输出
对每组输入,一行输出这段街道还有多少棵树。

输入样例
500 3
150 300
100 200
470 471

输出样例
298

请问怎么设计算法


页首
 用户资料  
 
2 楼 
 文章标题 : Re: 一条c++题目,请问怎么设计算法
帖子发表于 : 2009-08-18 15:09 
头像

注册: 2006-07-02 11:16
帖子: 12522
地址: 廣州
送出感谢: 0 次
接收感谢: 8
线段树


_________________
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。


页首
 用户资料  
 
3 楼 
 文章标题 : Re: 一条c++题目,请问怎么设计算法
帖子发表于 : 2009-08-18 15:11 
头像

注册: 2007-03-02 17:36
帖子: 7259
送出感谢: 3
接收感谢: 97
作业?


_________________
虽然世上没有完美的东西,但这并不影响我们追求完美,因为只有偏执狂才TMD能成功。
10.04新手入门——笨兔兔讲述自己的故事


页首
 用户资料  
 
4 楼 
 文章标题 : Re: 一条c++题目,请问怎么设计算法
帖子发表于 : 2009-08-18 17:42 

注册: 2008-10-06 22:19
帖子: 85
送出感谢: 0 次
接收感谢: 0 次
不好意思,刚没看清题目
代码:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
   int nStreet, nArea;
   cin >> nStreet >> nArea;
   nStreet ++; // 500米的街道共501树
   vector<bool> ToCut(nStreet, false);
   for (int i = 0; i < nArea; i++)
   {
      int nStart, nStop;
      cin >> nStart >> nStop;
      for (int j = nStart; j <= nStop; j++) ToCut[j] = true;
   }
   nStreet -= count(ToCut.begin(), ToCut.end(), true);
   cout << nStreet << endl;
   return 0;
}


_________________
个人博客:http://blog.csdn.net/yangzhuoluo


最后由 clarkyzl 编辑于 2009-08-18 17:57,总共编辑了 2 次

页首
 用户资料  
 
5 楼 
 文章标题 : Re: 一条c++题目,请问怎么设计算法
帖子发表于 : 2009-08-18 17:45 
头像

注册: 2006-01-06 17:26
帖子: 198
送出感谢: 0 次
接收感谢: 0 次
好难哦 看都看不懂


_________________
我是学习linux,不是学习如何装linux。

Myblog


页首
 用户资料  
 
6 楼 
 文章标题 : Re: 一条c++题目,请问怎么设计算法
帖子发表于 : 2009-08-18 19:18 

注册: 2009-01-07 15:19
帖子: 153
送出感谢: 1
接收感谢: 0 次
传说中的校门外的树 :em05 :em06


_________________
大家好,我是计算机系大学生,玩电脑也 7.8 年了吧,可是这个系统为什么XXX,就不能XXX,连我这种XXX都XXX,怎么能够推广,看来XXX路还很长XXX,搞不懂你们这些XXX,再见了XXX


页首
 用户资料  
 
7 楼 
 文章标题 : Re: 一条c++题目,请问怎么设计算法
帖子发表于 : 2009-08-19 12:18 
头像

注册: 2009-03-19 8:39
帖子: 185
送出感谢: 0 次
接收感谢: 0 次
是题目
还是考试题目
不过考试时没写起来,现在再来看看


页首
 用户资料  
 
8 楼 
 文章标题 : Re: 一条c++题目,请问怎么设计算法
帖子发表于 : 2009-08-19 12:25 
头像

注册: 2008-11-29 22:56
帖子: 578
地址: Guangdong Pharmaceutical University
送出感谢: 0 次
接收感谢: 0 次
没记错的话是NOIP普及组的题目吧?


_________________
猪圈里的猪想着去解放全世界


页首
 用户资料  
 
9 楼 
 文章标题 : Re: 一条c++题目,请问怎么设计算法
帖子发表于 : 2009-08-19 13:55 
头像

注册: 2009-03-19 8:39
帖子: 185
送出感谢: 0 次
接收感谢: 0 次
4楼真厉害啊
我把你的程序稍微修改的更符合题意,然后再提交上去,对了。而且运算时间短,占内存小。但写的这个程序我看不懂,algorithm和vector头文件也没看过,什么作用也不懂,如果有谁能说说,感激不尽。


页首
 用户资料  
 
10 楼 
 文章标题 : Re: 一条c++题目,请问怎么设计算法
帖子发表于 : 2009-08-19 16:24 
头像

注册: 2009-03-19 8:39
帖子: 185
送出感谢: 0 次
接收感谢: 0 次
tregedie 写道:
没记错的话是NOIP普及组的题目吧?

这是我们的期末考试题目


页首
 用户资料  
 
11 楼 
 文章标题 : Re: 一条c++题目,请问怎么设计算法
帖子发表于 : 2009-08-19 22:46 
头像

注册: 2008-11-29 22:56
帖子: 578
地址: Guangdong Pharmaceutical University
送出感谢: 0 次
接收感谢: 0 次
rob2468 写道:
tregedie 写道:
没记错的话是NOIP普及组的题目吧?

这是我们的期末考试题目

原题是NOIP 2005 普及组复赛第二题
:em04


_________________
猪圈里的猪想着去解放全世界


页首
 用户资料  
 
12 楼 
 文章标题 : Re: 一条c++题目,请问怎么设计算法
帖子发表于 : 2009-08-20 7:33 
头像

注册: 2009-03-19 8:39
帖子: 185
送出感谢: 0 次
接收感谢: 0 次
tregedie 写道:
rob2468 写道:
tregedie 写道:
没记错的话是NOIP普及组的题目吧?

这是我们的期末考试题目

原题是NOIP 2005 普及组复赛第二题
:em04


原来如此


页首
 用户资料  
 
显示帖子 :  排序  
发表新帖 回复这个主题  [ 12 篇帖子 ] 

当前时区为 UTC + 8 小时


在线用户

正在浏览此版面的用户:没有注册用户 和 3 位游客


不能 在这个版面发表主题
不能 在这个版面回复主题
不能 在这个版面编辑帖子
不能 在这个版面删除帖子
不能 在这个版面提交附件

前往 :  
本站点为公益性站点,用于推广开源自由软件,由 DiaHosting VPSBudgetVM VPS 提供服务。
我们认为:软件应可免费取得,软件工具在各种语言环境下皆可使用,且不会有任何功能上的差异;
人们应有定制和修改软件的自由,且方式不受限制,只要他们自认为合适。

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
简体中文语系由 王笑宇 翻译