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

多处最优服务次序问题

问题描述:设有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

思路分析：

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

具体步骤：

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

调试分析：

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

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

total_waiting_time += windows[min_idx] + serve_time[i];

#include <stdio.h>
#include <stdlib.h>

//比较函数，用于排序
int compare(const void *a,const void *b){
    return (*(int *)a - *(int *)b);
}

int main(){
    int n, s, total = 0;
    /*在 VS Code 中调试时，默认的工作目录是项目根目录（D:\myvscode)
    FILE *inputFile = fopen("input.txt", "r");
    FILE *outputFile = fopen("output.txt", "w");*/
    FILE *inputFile = fopen("D:/myvscode/daer2_suanfa/input.txt", "r");
    FILE *outputFile = fopen("D:/myvscode/daer2_suanfa/output.txt", "w");
    if(inputFile == NULL || outputFile == NULL){
        printf("文件打开失败！\n");
        return 1;
    }
    fscanf(inputFile, "%d %d", &n, &s);
    //读取服务时间
    int *serve_time = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n;i++){
        fscanf(inputFile, "%d", &serve_time[i]);
    }
    fclose(inputFile);
    //将服务时间按升序排序
    qsort(serve_time, n, sizeof(int), compare);
    //创建一个数组来存储每个窗口的服务时间
    int *windows = (int *)malloc(s * sizeof(int));
    for (int i = 0; i < s; i++) {
        windows[i] = 0; // 初始化每个窗口的结束时间
    }
    //遍历每个顾客
    for (int i = 0; i < n;i++){
        int min_window = 0;
        for (int j = 0; j < s;j++){ //遍历每个窗口找最短服务时间的窗口
            if(windows[j]<windows[min_window]){
                min_window = j;
            }
        }
        total += windows[min_window] + serve_time[i];//增加等待时间
        windows[min_window] += serve_time[i];//更新窗口时间
    }
    int average = total / n;
    fprintf(outputFile, "%d\n", average);
    fclose(outputFile);
    free(serve_time);//释放内存
    free(windows);
    return 0;
}

删数问题

问题描述:给定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

思路分析：

1. 贪心策略：

从左到右遍历数字，如果当前数字比下一个数字大，就删除当前数字（因为这样可以让后面的更小的数字前移）。

重复这个过程 k 次，直到删除 k 个数字。

特殊情况：

如果数字已经是升序（如 12345），直接删除最后 k 位。

如果 k 次删除未完成，但已经无法找到更大的数字（如 1111），直接删除末尾剩余的数字。

1. 实现方法：

使用 栈（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 读取数据）。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void removeK(char *num,int k){
    int n = strlen(num);
    if(k>=n){
        printf("0\n");
        return;
    }
    char *stack = (char *)malloc((n + 1) * sizeof(char));
    int top = -1;//栈顶指针
    for (int i = 0; i < n;i++){
        while(top>=0 && num[i]<stack[top] && k>0){
            top--;
            k--;
        }
        stack[++top] = num[i];//压入当前数字
    }
    top -= k;//top-k=top,如果还有剩余的k，从末尾删除
    //处理前导0
    int start = 0;//表示stack起始位置
    while(stack[start]=='0' && start<=top){//循环检查stack开头是否是 '0'
        start++;
    }
    //输出结果
    if(start>top){
        printf("0");//如果全部是0，输出0
    }else{
        for (int i = start; i <= top;i++){
            printf("%c", stack[i]);//否则输出非前导0部分
        }
    }
    printf("\n");
    free(stack);
}
int main(){
    FILE *inputFile = fopen("input.txt", "r");
    FILE *outputFile = fopen("output.txt", "w");
    if (inputFile == NULL || outputFile == NULL){
        printf("文件打开失败！\n");
        return 1;
    }
    char num[10000];
    int k;
    fscanf(inputFile, "%s", num);
    fscanf(inputFile, "%d", &k);
    fclose(inputFile);
    removeK(num, k);
    //由于 removeK 直接打印，可以重定向到文件
    freopen("output.txt", "w", stdout);//将标准输出重定向到文件 output.txt
    removeK(num, k);//调用函数，所有 printf 都写入文件
    fclose(outputFile);
    return 0;
}