Kattis - entertainmentbox
题目链接:https://vjudge.net/problem/Kattis-entertainmentbox
题目大意:
一种叫做不知道什么的盒子可以同时录 k 个节目,现给出 n 个节目的开始和结束时间,这个盒子最多能 “完整地” 录下多少个节目?
解题思路:
贪心。
训练的时候第一眼看见这道题就想起了《挑战》里面提到的 “区间调度问题”,乍看之下二者真的极为相似,但其实里面也有不同之处,但我的思维也被此局限住了。唉,弄了半天也弄不出个所以然,后来看了别人的题解才发现了自己哪里错了,真的好烦啊。感觉最近几天有点浮躁,要静下心来呀,骚年。
首先,将 n 个节目根据结束时间由早到晚排序这一点应该是很明确的,我们应该尽可能地选择早结束的,读者可以去翻阅一下《挑战程序设计竞赛》中的 “区间调度问题”。接下来的做法,我一开始是这么想的:弄一个队列,保存所有已经选取的节目的结束时间。一开始先让排序好的前 k 个结束时间入队。后来再让新节目入队的时候,如果它的开始时间晚于队首的结束时间,那么 pop 队首,让新节目的结束时间入队。后来想想自己真的是 too native. 随便一组数据就能推翻:
n=3,k=2.
1 10
2 5
6 9
后来又改变了几次思路,但通通不对,因为我没有抓住问题的本质,真的好燥啊!!!
其实这道题真正的贪心法则,应该是:每次选择是否要录制一个节目的时候,要从正在录制的队列中选择一个结束时间 “最接近” 我们正在考虑的节目的开始时间的节目,将这个节目从队列中 erase 掉,再把正在考虑的节目加进去。如果已有队列中所有节目的结束时间都在我们正考虑的节目的开始时间之后,那么如果已有队列中的节目小于 k,那么就直接把正在考虑的节目加入队列,否则的话就 continue.
实现方面,我是用 vector 和 upper_bound,一开始在 vector 中放入 k 个 0,代表没有节目正在录制。请看代码。
AC代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=;
typedef pair<int,int> P;
P rec[maxn];
bool cmp(const P &a,const P &b){
if(a.second==b.second) return a.first>b.first;
return a.second<b.second;
}
int main()
{
vector<int> que;
vector<int>::iterator iter;
int n,k;
scanf("%d%d",&n,&k);
for(int i=;i<n;i++) scanf("%d%d",&rec[i].first,&rec[i].second);
sort(rec,rec+n,cmp);
int ans=;
for(int i=;i<k;i++) que.push_back();
for(int i=;i<n;i++){
iter=upper_bound(que.begin(),que.end(),rec[i].first);
if(iter!=que.begin()){
que.erase(iter-);
que.push_back(rec[i].second);
ans++;
}
}
printf("%d\n",ans);
return ;
}
最新文章
- - >; code vs 3038 3n+1问题(递归)
- 38、重新复习javascript之三
- 表x有 一列 ,程序每次生成id的时候都先从这里获取最大值再加1,初始值是A0001,然后到A9999的时候则是到B0001 共5位
- [置顶] TortoiseGit和msysGit安装及使用笔记(windows下使用上传数据到GitHub)
- 第五次实验报告 java 网络编程
- error_log() 范例
- Typed Message模式与Event Sourcing
- UVa 11762 (期望 DP) Race to 1
- UVa 1103 (利用连通块来判断字符) Ancient Messages
- openstack kilo版本控制节点异常流量分析
- 有空可以对C#尝一下鲜,WCF看上去很诱人(跨进程、跨机器、跨子网,跨企业网乃至跨Internet的分布式服务)
- C++ Primer高速入门之三:几种常见的控制语句
- Android + Eclipse + PhoneGap 环境配置
- 【优秀的图片后期编辑工具】Luminar 3.1 for Mac
- 2018-2019-2 20165325《网络对抗技术》Exp0 Kali安装 Week1
- Spring Boot SSL
- shell编程—简介(一)
- 【python】spark+kafka使用
- JavaScript基础笔记(十一)JSON
- #科委外文文献发现系统——导出word模板1.0