贪心算法：多处最优服务次序、删数题目

多处最优服务次序题目

题目描述:设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti(1≤i≤n)，共有s处可以提供此项服务。应如何安排n个顾客的服务次序,才能使平均等待时间到达最小?平均等待时间是n个顾客等待服务时间的总和除以n。
算法计划:对于给定的n个顾客需要的服务时间和s的值，盘算最优服务次序。
数据输入:由文件input.txt给出输入数据。第1行有2个正整数n和s，表示有n个顾客且有s处可以提供顾客需要的服务。接下来的1行中有n个正整数，表示n个顾客需要的服务时间。
结果输出:将盘算的最小平均等待时间输出到文件output.txt。
输入文件示例input.txt
10 2
56 12 1 99 1000 234 33 55 99 812
输出文件示例output.txt
336
思路分析：

• 贪心算法：优先安排服务时间较短的顾客，减少其他顾客的等待时间
  
• 多窗口调度：将顾客分配到当前累计等待时间最少的窗口
  
• 平均等待时间盘算：全部顾客等待时间的总和除以顾客数量
  

具体步骤：

• 将顾客按服务时间从短到长排序
  
• 初始化s个服务窗口，每个窗口的累计服务时间为0
  
• 对于每个顾客，将其分配到当前累计服务时间最少的窗口
  
• 将该顾客的服务时间加到该窗口的累计服务时间中
  
• 将该顾客的等待时间（即分配前的窗口累计服务时间）加入总等待时间
  
• 末了盘算平均等待时间
  

调试分析：

• 调试时VS Code默认的工作目录是项目根目录（D:\myvscode），因此用相对路径打开input.txt会显示文件打开失败，此时可以将文件路径切换为绝对路径。
  
• /：整除，向下取整，不会四舍五入，截断掉了小数部门，向零取整。
  
• 标题中的“等待时间”是指顾客从开始等到服务竣事的总时间。即：等待时间 = 开始服务时间 + 自己的服务时间。
  

total_waiting_time += windows[min_idx];应改为：
total_waiting_time += windows[min_idx] + serve_time;

1. #include <stdio.h>
2. #include <stdlib.h>
4. //比较函数，用于排序
5. int compare(const void *a,const void *b){
6.     return (*(int *)a - *(int *)b);
7. }
9. int main(){
10.     int n, s, total = 0;
11.     /*在 VS Code 中调试时，默认的工作目录是项目根目录（D:\myvscode)
12.     FILE *inputFile = fopen("input.txt", "r");
13.     FILE *outputFile = fopen("output.txt", "w");*/
14.     FILE *inputFile = fopen("D:/myvscode/daer2_suanfa/input.txt", "r");
15.     FILE *outputFile = fopen("D:/myvscode/daer2_suanfa/output.txt", "w");
16.     if(inputFile == NULL || outputFile == NULL){
17.         printf("文件打开失败！\n");
18.         return 1;
19.     }
20.     fscanf(inputFile, "%d %d", &n, &s);
21.     //读取服务时间
22.     int *serve_time = (int *)malloc(n * sizeof(int));
23.     for (int i = 0; i < n;i++){
24.         fscanf(inputFile, "%d", &serve_time[i]);
25.     }
26.     fclose(inputFile);
27.     //将服务时间按升序排序
28.     qsort(serve_time, n, sizeof(int), compare);
29.     //创建一个数组来存储每个窗口的服务时间
30.     int *windows = (int *)malloc(s * sizeof(int));
31.     for (int i = 0; i < s; i++) {
32.         windows[i] = 0; // 初始化每个窗口的结束时间
33.     }
34.     //遍历每个顾客
35.     for (int i = 0; i < n;i++){
36.         int min_window = 0;
37.         for (int j = 0; j < s;j++){ //遍历每个窗口找最短服务时间的窗口
38.             if(windows[j]<windows[min_window]){
39.                 min_window = j;
40.             }
41.         }
42.         total += windows[min_window] + serve_time[i];//增加等待时间
43.         windows[min_window] += serve_time[i];//更新窗口时间
44.     }
45.     int average = total / n;
46.     fprintf(outputFile, "%d\n", average);
47.     fclose(outputFile);
48.     free(serve_time);//释放内存
49.     free(windows);
50.     return 0;
51. }

复制代码

删数题目

题目描述:给定n位正整数a，去掉此中任意k≤n个数字后，剩下的数字按原次序分列组成一个新的正整数。对于给定的n位正整数a和正整数k，计划一个算法找出剩下数字组成的新数最小的删数方案。
算法计划:对于给定的正整数a，盘算删去k个数字后得到的最小数。
数据输入:由文件input.txt提供输入数据。文件的第1行是1个正整数a。第2行是正整数k。
结果输出:将盘算的最小数输出到文件output.txt。
输入文件示例
input.txt
178543
4
输出文件示例
output.txt
13
思路分析：

• 贪心策略：
  

从左到右遍历数字，如果当前数字比下一个数字大，就删除当前数字（因为如许可以让后面的更小的数字前移）。
重复这个过程 k 次，直到删除 k 个数字。
特殊情况：
如果数字已经是升序（如 12345），直接删除末了 k 位。
如果 k 次删除未完成，但已经无法找到更大的数字（如 1111），直接删除末尾剩余的数字。

• 实现方法：
  

使用 栈（Stack） 来模拟删除过程：
1.遍历数字的每一位。
2.如果当前数字比栈顶的数字小，并且还可以删除（k > 0），就弹出栈顶数字（相当于删除），并减少 k。
3.否则，将当前数字压入栈。
4.如果遍历完成后 k 仍然大于 0，则从末尾删除剩余 k 个数字。
调试分析：

• 遍历数字 O(n)，每个数字最多入栈和出栈一次，因此总时间复杂度为 O(n)。
  
• 边界情况：
  
  
  
  • k = 0：直接返回原数字。
    
  • k = n：返回 0。
    
  • 数字有前导 0（如 1001 删除 2 位后得到 00，应输出 0）。
    
  
  
• 特殊注意 前导零 和 剩余 k 未删完 的情况。可以使用 printf 打印中间变量（栈状态）调试。
  
• 前导0题目：例如，输入10200，删除1位后得到0200，应表示200。设置start指针循环检查。
  
• 重定向
  

重定向 是指改变程序默认的输入/输出（I/O）方向。通常：

• 标准输入（stdin）：默认是键盘输入。
  
• 标准输出（stdout）：默认是屏幕（控制台）输出。
  
• 标准错误（stderr）：默认也是屏幕输出。
  

重定向的作用：

• 把程序的输出从屏幕 重定向 到文件（如 output.txt）。
  
• 也可以把文件的输入 重定向 到程序（如从 input.txt 读取数据）。
  

1. #include <stdio.h>
2. #include <string.h>
3. #include <stdlib.h>
4. void removeK(char *num,int k){
5.     int n = strlen(num);
6.     if(k>=n){
7.         printf("0\n");
8.         return;
9.     }
10.     char *stack = (char *)malloc((n + 1) * sizeof(char));
11.     int top = -1;//栈顶指针
12.     for (int i = 0; i < n;i++){
13.         while(top>=0 && num[i]<stack[top] && k>0){
14.             top--;
15.             k--;
16.         }
17.         stack[++top] = num[i];//压入当前数字
18.     }
19.     top -= k;//top-k=top,如果还有剩余的k，从末尾删除
20.     //处理前导0
21.     int start = 0;//表示stack起始位置
22.     while(stack[start]=='0' && start<=top){//循环检查stack开头是否是 '0'
23.         start++;
24.     }
25.     //输出结果
26.     if(start>top){
27.         printf("0");//如果全部是0，输出0
28.     }else{
29.         for (int i = start; i <= top;i++){
30.             printf("%c", stack[i]);//否则输出非前导0部分
31.         }
32.     }
33.     printf("\n");
34.     free(stack);
35. }
36. int main(){
37.     FILE *inputFile = fopen("input.txt", "r");
38.     FILE *outputFile = fopen("output.txt", "w");
39.     if (inputFile == NULL || outputFile == NULL){
40.         printf("文件打开失败！\n");
41.         return 1;
42.     }
43.     char num[10000];
44.     int k;
45.     fscanf(inputFile, "%s", num);
46.     fscanf(inputFile, "%d", &k);
47.     fclose(inputFile);
48.     removeK(num, k);
49.     //由于 removeK 直接打印，可以重定向到文件
50.     freopen("output.txt", "w", stdout);//将标准输出重定向到文件 output.txt
51.     removeK(num, k);//调用函数，所有 printf 都写入文件
52.     fclose(outputFile);
53.     return 0;
54. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。