hdoj2037 贪心算法——今年暑假不AC
2024-08-25 00:06:04
所谓“贪心算法”是指:在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。
经典问题:时间序列问题 点击打开链接 hdoj2037
解题思路:按照题目尽可能多看节目的要求,在证明贪心算法在此题的适用性后,将t[i]按照结束时间e进行排序,以总是选择开始时间大于等于上一个节目的结束时间并且自身结束时间早的节目。
源代码:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
struct T
{
int s;
int e;
}t[101];
int cmp(T x,T y)
{
return x.e<y.e;
} int main()
{
int n;
int i;
while(cin>>n&&n)
{
for(i=0;i<n;i++)
{
cin>>t[i].s>>t[i].e;
}
sort(t,t+n,cmp);
int tmp = t[0].e;
int cnt = 1;
for(i=1;i<n;i++)
{
if(t[i].s>=tmp)
{
cnt++;
tmp = t[i].e;
} }
cout<<cnt<<endl;
} return 0;
}
最新文章
- 《Note --- Unreal 4 --- Sample analyze --- StrategyGame(continue...)》
- CRYPTO-MD5
- java使用httpcomponents post发送json数据
- IE 兼容模式下不支持DIV CSS样式display:inline-block,解决
- pycurl
- ps教程-三分钟画齿轮
- android 开发过程中碰到的 Failed to create the part&#39;s controls 问题
- Solr配置与简单Demo
- (转)syslog日志等级
- TinyXML用法小结
- Mesos+Zookeeper+Marathon+Docker分布式集群管理最佳实践
- 由于用mpu6050模块,所以要用上i2c通信原理。
- jQuery使用serialize(),serializeArray()方法取得表单数据+字符串和对象类型两种表单提交的方法
- 利用USearch去除嵌合体(chimeras)
- 转发:RSA实现JS前端加密,PHP后端解密
- Codeforces Codeforces Round #484 (Div. 2) D. Shark
- opencv 进行图像的花屏检测(模糊检测)
- maven配置(myeclipse版)
- benthos 通过配置文件配置 stream 说明
- Nmap用法实例
热门文章
- Windows Serverserver结束MySQL自己主动数据库备份
- Chrome扩展,应用开发学习笔记之2---恶搞百度一下
- 张汝京:CIDM模式进可攻、退可守,建议尝试
- Windows下程序打包发布时的小技巧(使用Dependency Walker侦测不理想,改用VS自带的dumpbin则万无一失,还可查看dll导出的函数)
- C++该typeid和dynamic_cast
- AngularJS 计时器
- 自定义函数Function
- jQuery省市联动
- 简单实用SQL脚本Part:查找SQL Server 自增ID值不连续记录
- Win10《芒果TV》商店版更新v3.2.5:新增会员频道,修复多处细节问题,小年快乐