【贪心法】程序存储问题

简介: 【贪心法】程序存储问题

 题目描述:

设有n个程序{1,2,…, n }要存放在长度为L 的磁带上。程序i存放在磁带上的长度是li,1≤i≤n 。程序存储问题要求确定这n个程序在磁带上的一个存储方案,使得能够在磁带上存储尽可能多的程序。

编程任务:

  对于给定的n 个程序存放在磁带上的长度,编程计算磁带上最多可以存储的程序数。

数据输入:

  (由文件input.txt 给出输入数据。)第一行是2个正整数,分别表示文件个数n 和磁带的长度L。接下来的1行中,有n个正整数,表示程序存放在磁带上的长度。

结果输出:

  将编程计算出的最多可以存储的程序数输出(到文件output.txt)

输入文件示例输出文件示例

input.txt                        output.txt

6 50                             5

2 3 13 8 80 20

注:若题目要求含上述括号中橙色字体,即将代码第11、12行注释解除,让其执行即可。

代码如下:

#include <iostream>
#include <algorithm>//sort()头文件 
#include <fstream>//文件读写操作头文件 
using namespace std;
#define N 10000
bool cmp(int x,int y){
  return x<y;
}
int main(){
  //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
  int n,L; cin>>n>>L;//输入文件个数,磁带长度
  int Long[N];
  for(int i=0;i<n;i++){
    cin>>Long[i];
  } 
  sort(Long,Long+n,cmp);//以升序排列 
  int flag=0;//记录存储第flag个程序,flag从0开始(数组存储从0开始) 
  int LongSum=0;//记录存储的程序长度和 
  int Num=0;//记录存储的程序个数 
  while(flag<n){
    LongSum=LongSum+Long[flag];//求和 
    if(LongSum>L) break;//超出磁带长度,跳出循环 
    else Num++;
    flag++; 
  }
  cout<<Num<<endl;
  return 0;
}

image.gif


目录
相关文章
|
存储 JSON SpringCloudAlibaba
Sentinel使用及规则配置
Sentinel使用及规则配置
2403 0
Sentinel使用及规则配置
|
SQL 前端开发 JavaScript
分享几个开源Java写的博客系统
分享几个开源Java写的博客系统
5866 0
分享几个开源Java写的博客系统
|
XML 数据安全/隐私保护 数据格式
批量获取FreeSWITCH所有分机号及其密码
批量获取FreeSWITCH所有分机号及其密码
218 0
|
算法 测试技术 编译器
【算法】优先队列式分支限界法,以01背包问题为例
📑 例题:01背包问题 题目链接:采药-洛谷 当洛谷上不让下载测试用例,可以试试:采药-ACWing
1711 0
|
应用服务中间件 网络架构
kodexplorer私有云本地部署,低成本内网穿透教程
可搭建:网站或个人博客;类似于某云的网盘;远程路由器(等家电)控制,内网的服务穿透至外网;迅雷远程下载;家庭云存储中心等。准备工作: 1、 可以插U盘的路由器(推荐二手小米mini,40包邮不能再多了) 2、 将路由器刷为最新的老毛子固件(参见恩山无线论坛) 3、 掏钱买VPS或者寻找一个免费的FRPS服务器 搭建步骤简述: 1、 路由器,联网,插U盘(事先格式化为EXT4格式,可以用diskgenius免费版)。
6963 1
|
Android开发 iOS开发
Flutter应用开发,系统样式改不了?SystemChrome 状态栏、导航栏、屏幕方向……想改就改
Flutter应用开发,系统样式改不了?SystemChrome 状态栏、导航栏、屏幕方向……想改就改
|
缓存 安全 数据库
构建简单博客系统:从数据库设计到性能优化实践
本文以构建简单博客系统为例,详细介绍了从数据库设计与建模到性能调优与扩展的全过程。通过丰富的代码示例,读者将全面了解如何设计数据库模型、实现数据库操作和查询优化,以及如何实现用户认证与权限控制,最终实现一个高效、安全的博客系统。
593 0
|
安全 大数据 网络安全
阿里云国际版免实名注册账号,支持多种支付方式
阿里云国际版账号是需要通过阿里云渠道商来实现注册认证的,本篇文章就介绍一家这样的阿里云国际版渠道商1788yun.com,通过它,实现无需PayPal信用卡,无门槛注册买阿里云国际版的产品与服务。
阿里云国际版免实名注册账号,支持多种支付方式
|
存储 Prometheus 运维
阿里云ES全观测引擎TimeStream时序增强功能重磅发布,助力时序场景实现最佳实践
阿里云ES全观测引擎TimeStream时序增强功能最新发布,在云原生ELK全托管基础上,通过TimeStream时序增强功能插件,可实现高性能、低成本时序数据存储和查询分析。本文介绍TimeStream适用场景、功能优势、性能测试结果和实践案例
2562 0