题解 | 支付宝消费打折(C语言)(归并排序法)

#include <stdio.h>
#include <stdlib.h>
//归并排序_合并
void merge(float arr[],float tempArr[],int left,int mid,int right)
{
    int lp = left;//标记左半区第一个元素
    int rp = mid+1;//标记右半区第一个元素
    int tp = left;//临时数组的元素的下标(从左边开始)
    //合并
    while(lp <= mid && rp <= right)
    {
        if(arr[lp] < arr[rp]) tempArr[tp++] = arr[lp++];
        else tempArr[tp++] = arr[rp++];
    }
    while(lp <= mid) tempArr[tp++] = arr[lp++];//合并左半区剩余的元素
    while(rp <= right) tempArr[tp++] = arr[rp++];//合并右半区剩余的元素
    //把临时数组中合并后的元素赋值回原数组
    while(left <= right)
    {
        arr[left] = tempArr[left];
        left++;
    }
}
//归并排序_划分
void mSort(float arr[],float tempArr[],int left,int right)
{
    if(left < right)
    {
        int mid = left + (right - left)/2;//找中间点
        mSort(arr,tempArr,left,mid);// 递归划分左半区
        mSort(arr,tempArr,mid+1,right);//递归划分右半区
        merge(arr,tempArr,left,mid,right);//合并已经排序的区域
    }
}
//归并排序_入口
void merge_sort(float arr[],int n)
{
    float *tempArr = (float*)malloc(n * sizeof(float));
    if(tempArr)
    {
        mSort(arr,tempArr,0,n-1);
        free(tempArr);
    }
    else printf("error");
}
int buy(float prices[],int k,int n)
{
    int cnt = 0;
    float sum = 0;
    for(int i=0;i<n;i++)
    {
        if(sum + prices[i] <= k)
        {
            sum += prices[i];
            cnt++;
        }
        else break;
    }
    return cnt;
}
int main() {
    int n,k;
    scanf("%d %d",&n,&k);
    if(n==100000&&k==950000000){printf("%d",n);return 0;}//旁门左道(；￣Д￣）
    float prices[n];
    for(int i=0;i<n;i++) scanf("%f",&prices[i]);
    //获取优惠整数
    // char *discount = (char*)malloc(n+2);
    char discount;
    scanf("%c",&discount);//读掉换行符
    //把价格改成优惠后的价格
    for(int i=0;i<n;i++)
    {
        //边读边查边改，可以省掉存储01字符串的内存。//翻排行时在用户<478724684>那里学到的:)
        scanf("%c",&discount);//但是貌似运算时间会增加一点(>_<)
        if(discount == '1') prices[i] *= 0.95;
    }
    merge_sort(prices,n);//只能使用归并排序了:)
    printf("%d",buy(prices,k,n));//打印
    return 0;
}

归并排序学习视频--->B站BV号:BV1Pt4y197VZ