河北大学程序设计训练营

day09 程序存储问题

题目描述：

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

输入格式:

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

输出格式:

输出最多可以存储的程序数。

输入样例:

在这里给出一组输入。例如：

6 50

2 3 13 8 80 20

输出样例:

在这里给出相应的输出。例如：

5

解题思路：

在特定大小的磁带上存下尽可能多的程序，所以依次放入最小文件即可。

关键点：对程序大小的排序

参考答案：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

using namespace std;

int main() {
	int n, m;
  cin >> n >> m;
  int num[n];
  
  // 输入程序大小
  for(int i = 0; i < n; ++i) {
    cin >> num[i];
  }
  
  // 使用sort函数对程序大小进行排序
  sort(num, num + n);
  
  // 变量i有两个作用：
  // 1、存储程序的个数
  // 2、作为遍历的变量
  int i = 0;
  for(; i < n; ++i) {
    
    // 如果可以存下
    if(m >= num[i]) {
			m = m - num[i];
    } 
    
    // 如果不能存下
    else {
			break;
    }
    
  }
	// 输出
  cout << i;
}

变量i的作用可以好好琢磨一下。

补充：sort函数

函数结构：

cpp
1
sort(begin，end，cmp);

参数含义：

  • begin：要排序数组的起始地址。
  • end：要排序数组结束地址的下一位。
  • cmp：比较器，实际上就是返回值为布尔值的函数。用于规定排序的方法，可不填，默认升序。

⚠️注意：begin和end是地址！！地址！！！

使用示例：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>

// 定义由大到小排列
bool cmp(int a, int b) {
	return a > b;
}

int main () {
  int a[5] = {2, 4, 3, 5, 1};
  
  sort(a, a + 5);
  
  for (int i = 0; i < 5; ++i) {
    printf("%d", a[i]);
  }
}

运行输出：

1 2 3 4 5

其中需要注意的是：sort()不保证保持相等元素的顺序。（不明白的可以在群里问哈😏）

此外，比较器也常用于定义结构体的排列规则，详细用法可以参考这个例题：PTA 德才论（结构体的sort）