时间限制:1000MS 代码长度限制:10KB
提交次数:25 通过次数:9
题型: 编程题 语言: G++;GCC;VC;JAVA
现在n个视频流要在一条通信链路上一个接一个的传送。视频流i由bi位组成,这些位需要一个常数速率,
在ti秒内被发送。你不可能同时发送两个视频流,因此需要确定一个关于视频流的调度。
无论你选择哪一个次序,在一个视频流的结束与下一个视频流开始之间不能有任何延迟。假如你调度在时
刻0开始,无论采用什么次序,都将结束于sum{ ti | i from 1 to n}这个时刻。我们假设所有的bi和ti都
是正整数。
现在引入一个链路限制参数r。由于你仅仅是一个用户,这个链路不想让你占用太多的带宽,因此规定这个限制
条件:对每个自然数t>0,你在从0到t的时间区间内发送的总位数不能超过rt。这个规定是对开始于0的时间区间
的,而不是开始于任何别的时间区间的。满足这个限制的调度才是有效的。
给定n个视频流,每个视频流位数bi,持续时间ti,以及链路限制参数r。比如,n=3个视频流,具有:
(b1,t1)=(2000,1)
(b2,t2)=(6000,2)
(b3,t3)=(2000,1)
链路限制参数r=5000。
则按照1,2,3的次序运行这个视频流的调度室有效的,因为:
t=1:第1个视频流全部被发送,且2000<50001
t=2:第2个视频流一半被发送,且2000+3000<50002
t=3与t=4,类似的结论也成立。
现在给出一个多项式运行时间的算法,确定是否存在一个有效调度?并输出这个有效调度。
第一行:n r (n表示视频流个数,r表示链路限制参数,中间空格,n<10000,r>0)
接下来n行,都是这样组合:bi ti 1<=i<=n
n个视频流有效的调度顺序(这个调度顺序不一定唯一,我们优先输出字典序排前的那一种调度)。
若不存在有效的调度顺序,输出“no”(无大写无标点)。
3 5000
2000 1
6000 2
2000 1
1 2 3
由于题目要求是 优先输出的是“字典序”最小的有效调度,所以贪心思想也是比较容易想到的,即:每次都从头往后找,找到第一个满足视频流调度条件的,就进行记录,然后重新从头往后找,直到所有视频流都记录为止(即所有视频流都已发送)。
更多注释可查看下方的完整代码中,有助于理解。
#include
#include
#include
#include
#include
#include
using namespace std;
int byte[10001];
int Time[10001];
vector<int> num; // 存各视频流编号,即 cur,要输出的
int v[10001]; // v[i] 用于标记数字是否被选中
int main()
{
int i, j, n, r;
cin >> n >> r;
for(i = 1; i <= n; i++) {
cin >> byte[i] >> Time[i];
}
int currentByte = 0; // 当前视频流总数
int currentClock = 0; // 当前消耗的时间单位数
// 当前要输出的数组记录了几位编号了
for(i = 1; i <= n; i++) {
int flag = 0; // 用于表示本轮从头往后找,有无找到满足视频流调度的序号
for(j = 1; j <= n; j++) {
// 该视频流没被选过且加上该视频流后,字节还在范围内,即找到满足条件的视频流了
if(!v[j] && currentByte + byte[j] <= (currentClock + Time[j]) * r) {
v[j] = 1;
flag = j;
break;
}
}
// 说明本轮从头往后找没找到满足视频流调度的序号,由于还没发完全部视频流,所以不满足
if(flag == 0) {
cout << "no" << endl;
return 0;
}
// 若找到视频流,进行相关的操作
currentByte += byte[j];
currentClock += Time[j];
num.push_back(j);
}
for(i = 0; i < n; i++) {
cout << num[i] << " ";
}
return 0;
}
此题我们的思想类似于全排列,也就是将所有序号按字典序从小到大排列出来,当找到第一个满足条件的序列,就停止算法。
但由于 n < 10000,所以该算法会超时,但也算是提供了一种新思路。
为什么要回溯呢?
因为我记录序号都共用一个 num 数组,在同一个循环内,如果你比如在索引为2时,想输出序号为3的情况,又想输出序号为4的情况,那就得想之前的给 “撤销” 了,再继续,同时标志数组也记得撤销哈
更多注释可查看下方的完整代码中,有助于理解。
#include
#include
#include
using namespace std;
int byte[10001];
int Time[10001];
int n, r;
//int sum = 0; // 前面的视频流总值
vector<int> num; // 存各视频流编号,即 cur,要输出的
int v[10001]; // v[i] 用于标记数字是否被选中
int flag = 0; // 如果 flag 为1,说明找到序列了,停止算法
void f(int cur, int sum, int clock) {
if(flag == 1)
return;
// 检查到最后一个看看满不满足调度了,如果还满足就不用递归了,直接输出并暂停算法
if(cur == n + 1) {
// 调度范围内
for(int i = 0; i < num.size(); i++) {
cout << num[i] << " ";
}
//cout << endl;
flag = 1;
return;
}
for(int i = 1; i <= n; i++) {
if(!v[i]) {
// 看看若加入当前编号的流,满不满足调度,如果还满足就继续递归了,否则直接剪枝
//cout << "cur=" << cur << " sum=" << sum << " byte=" << byte[cur] << " Time=" << Time[cur] << " clock=" << clock << endl;
if(sum + byte[i] <= r * (clock + Time[i])) {
v[i] = 1;
num.push_back(i);
f(cur + 1, sum + byte[i], clock + Time[i]);
num.pop_back();
v[i] = 0;
}
}
}
}
int main()
{
memset(v, 0, sizeof(v));
// 搜索+回溯+剪枝
cin >> n >> r;
for(int i = 1; i <= n; i++) {
cin >> byte[i] >> Time[i];
}
f(1, 0, 0);
// 如果执行完上面的算法,flag 还是0,即没有找到合适序列,那就输出 no
if(flag == 0) {
cout << "no" << endl;
}
return 0;
}