XYNUOJ 1253: 磁带最大利用率问题

朱雀 2024-02-18 22:03 62阅读 0赞

###    **1253: 磁带最大利用率问题** ###

时间限制: 1 Sec 内存限制: 128 MB  
提交: 83 解决: 50  
您该题的状态：**已完成**  
\[[提交][Link 1]\]\[[状态][Link 2]\]\[[讨论版][Link 3]\]

### **题目描述** ###

设有n个程序\{1,2，...,n\}要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1<=i<=n.

程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。在保证存储最多程序的前提下，要求磁带的利用率最大。

编程任务：对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数和占用磁带的长度。

### **输入** ###

第一行是2个正整数，分别表示文件个数n和磁带长度L。第二行中，有n个正整数，表示程序存放在磁带上的长度。

### **输出** ###

第一行输出最多可以存储的程序数和占用磁带的长度；第二行输出存放在磁带上的每个程序的长度，（输出程序次序应与输入数据次序保持一致）

### **样例输入** ###

9 50
 2 3 13 8 80 20 21 22 23

### **样例输出** ###

5 49
 2 3 13 8 23

### **提示** ###

贪心策略：最短程序优先。求得最多可以存储的程序个数m后，再求最大利用率。问题转化为第5章中的装载问题，但m已知。

### **来源** ###

[贪心][Link 4]

\#include<iostream> 
\#include<algorithm> 
\#include<cstdlib> 
using namespace std; 
struct kk 
\{ 
int s; 
int e; 
\}a\[100\],b\[100\]; 
int cmp2(struct kk x,struct kk y) 
\{ 
return x.s<y.s; 
\} 
int cmp1(struct kk x,struct kk y) 
\{ 
return x.e<y.e; 
\}

int main() 
\{ 
int n,m; 
int i,j=0,k,t,sum=0,max=0,f=0; 
struct kk w; 
scanf("%d %d",&n,&m); 
for(i=0;i<n;i++) 
\{ 
cin>>a\[i\].s; 
a\[i\].e=i; 
\} 
sort(a,a+n,cmp2); 
//for(i=0;i<n;i++) 
//cout<<a\[i\].s<<" "; 
//cout<<endl; 
for(i=0;sum<=m;i++) 
\{ 
if(sum+a\[i\].s+a\[i+1\].s>m) 
\{ 
t=m-sum; 
for(k=i;a\[k\].s<=t;k++) 
if(a\[k\].s>max) 
\{ 
max=a\[k\].s; 
w=a\[k\]; 
\} 
 
sum+=max; 
b\[j++\]=w; 
f++; 
//cout<<sum<<" "<<b\[j-1\].s<<endl; 
break; 
\} 
else 
\{ 
sum+=a\[i\].s; 
b\[j++\]=a\[i\]; 
f++; 
//cout<<sum<<" "<<b\[j-1\].s<<endl; 
\} 
 
 
if(sum>m) 
break; 
\} 
sort(b,b+j,cmp1); 
cout<<f<<" "<<sum<<endl; 
for(i=0;i<j;i++) 
if(i!=j-1) 
cout<<b\[i\].s<<" "; 
else 
cout<<b\[i\].s<<endl; 
return 0; 
 
 
\}

[Link 1]: http://xyoj.xynu.edu.cn/submitpage.php?id=1253
[Link 2]: http://xyoj.xynu.edu.cn/problemstatus.php?id=1253
[Link 3]: http://xyoj.xynu.edu.cn/bbs.php?pid=1253
[Link 4]: http://xyoj.xynu.edu.cn/problemset.php?search=%E8%B4%AA%E5%BF%83