三沣开发知识 购物 网址 游戏 小说 歌词 地图 快照 开发 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 编程 租车 短信 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题
autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml
html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
  IT知识库 -> C++ -> 洛谷P1607 [USACO09FEB]庙会班车Fair Shuttle -> 正文阅读
 

[C++]洛谷P1607 [USACO09FEB]庙会班车Fair Shuttle

洛谷P1607 [USACO09FEB]庙会班车Fair Shuttle 题目描述
Although Farmer John has no problems walking around the fair to collect prizes or see the shows, his cows are not in such good shape; a full day of walking around the fair leaves them exhausted. To help them enjoy the fair, FJ has arranged for a shuttle truck to take the cows from place to place in the fairgrounds.
FJ couldn't afford a really great shuttle, so the shuttle he rented traverses its route only once (!) and makes N (1 <= N <= 20,000) stops (conveniently numbered 1..N) along its path. A total of K (1 <= K <= 50,000) groups of cows conveniently numbered 1..K wish to use the shuttle, each of the M_i (1 <= M_i <= N) cows in group i wanting to ride from one stop S_i (1 <= S_i < E_i) to another stop E_i (S_i < E_i <= N) farther along the route.
The shuttle might not be able to pick up an entire group of cows (since it has limited capacity) but can pick up partial groups as appropriate.
Given the capacity C (1 <= C <= 100) of the shuttle truck and the descriptions of the groups of cows that want to visit various sites at the fair, determine the maximum number of cows that can ride the shuttle during the fair.
逛逛集市,兑兑奖品,看看节目对农夫约翰来说不算什么,可是他的奶牛们非常缺乏锻炼——如果要逛完一整天的集市,他们一定会筋疲力尽的。所以为了让奶牛们也能愉快地逛集市,约翰准备让奶牛们在集市上以车代步。但是,约翰木有钱,他租来的班车只能在集市上沿直线跑一次,而且只能停靠N(1 ≤N≤20000)个地点(所有地点都以1到N之间的一个数字来表示)。现在奶牛们分成K(1≤K≤50000)个小组,第i 组有Mi(1 ≤Mi≤N)头奶牛,他们希望从Si跑到Ti(1 ≤Si<Ti≤N)。
由于班车容量有限,可能载不下所有想乘车的奶牛们,此时也允许小里的一部分奶牛分开乘坐班车。约翰经过调查得知班车的容量是C(1≤C≤100),请你帮助约翰计划一个尽可能满足更多奶牛愿望的方案。
输入输出格式
输入格式:
【输入】
第一行:包括三个整数:K,N和C,彼此用空格隔开。
第二行到K+1行:在第i+1行,将会告诉你第i组奶牛的信息:Si,Ei和Mi,彼
此用空格隔开。
输出格式:
【输出】
第一行:可以坐班车的奶牛的最大头数。
输入输出样例
输入样例#1:

8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1

输出样例#1:

10

说明
【样例说明】
班车可以把2头奶牛从1送到5,3头奶牛从5送到8,2头奶牛从8送到14,1头
奶牛从9送到12,1头奶牛从13送到14,1头奶牛从14送到15。
zhw讲的做法是线段树
但是我想问,,
为什么暴力能过的题需要用线段树???????
思路:按照结束点排序,对于每一个线段,查询一下他在覆盖的区间里面的最小值,
   然后根据这条线段的权值进行分类讨论就好

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=100001;
inline void read(int &n)
{
	char c=getchar();bool flag=0;n=0;
	while(c<'0'||c>'9')	c=='-'?flag=1,c=getchar():c=getchar();
	while(c>='0'&&c<='9')	n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
}
struct node
{
	int bg,ed,num;
}cow[MAXN];
int comp(const node &a,const node &b)
{
	if(a.ed!=b.ed)	return a.ed<b.ed;
	else return a.bg<b.bg;
}
int have[MAXN];// 在i这个位置,车上已经装了多少奶牛 
int main()
{
	int k,n,m;
	read(k);read(n);read(m);
	for(int i=1;i<=k;i++)
		read(cow[i].bg),read(cow[i].ed),read(cow[i].num);
	sort(cow+1,cow+k+1,comp);
	int ans=0;
	for(int i=1;i<=k;i++)
	{
		if(have[cow[i].bg]>=m) continue;
		int now=0x7fffff;
		for(int j=cow[i].bg;j<=cow[i].ed;j++)
		{
			now=min(now,m-have[j]);
			if(now==0) break;
		}	
		if(now!=0)
		{
			if(now>=cow[i].num)
			{
				for(int j=cow[i].bg;j<cow[i].ed;j++)	
					have[j]+=cow[i].num;
				ans+=cow[i].num;
			}		
			else 
			{
				for(int j=cow[i].bg;j<cow[i].ed;j++)	
					have[j]+=now;
				ans+=now;
			}
		}
	}
	printf("%d",ans);
	return 0;
}

  
  C++ 最新文章
关于poin与references
019:别叫,这个大整数已经很简化了!
c++智能指针详解
BZOJ1269: [AHOI2006]文本编辑器editor
洛谷P3835 【模板】可持久化平衡树
洛谷P2925 [USACO08DEC]干草出售Hay For Sa
1267 老鼠的旅行 2012年CCC加拿大高中生信息
项目中进度条实现臆想
遗传算法
简单的传球游戏(矩阵)
上一篇文章           查看所有文章
加:2017-10-19 23:23:31  更:2017-10-19 23:24:04 
 
技术频道: 站长资讯 .NET新手区 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA Visual Studio ASP.NET MVC .NET控件开发 Entity Framework WinRT/Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动设计 Html/Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP Oracle ERP Dynamics CRM K2 BPM 信息安全 企业信息化其他 Android开发 iOS开发 Windows Phone Windows Mobile 其他手机开发 敏捷开发 项目与团队管理 软件工程其他 SQL Server Oracle MySQL NoSQL 其它数据库 Windows 7 Windows Server Linux
脚本语言: vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程
网站开发: CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2018年7日历
2018-7-20 6:38:03
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT知识库