[已解决]这个二分查找怎么做？

张育玮

如图

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2021-10-31 20:30:05

代码：

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

int sort(const void * elem1, const void * elem2) // 定义函数：用于进行排序
{
    int f = *((int*)elem1);
    int s = *((int*)elem2);
    if (f > s) return  1;
    if (f < s) return -1;
    return 0;
}

int main()
{
    int N, K, sum = 0;
    double s;
    scanf("%d %d", &N, &K);
    int a[N];
    for(int i = 1; i <= N; i++)
    {
        scanf("%lf", &s);
        a[i] = s*100;
    }
    qsort(a, sizeof(a)/sizeof(*a), sizeof(*a), sort); // 排序
    int res = 0, r = a[N]/100*100+1;
    while(res+1 < r)
    {
        int mid = (res+r)/2;
        for(int i = 1; i <= N; i++) sum += a[i]/mid;
        if(sum >= K) res = mid;
        else r = mid;
        sum = 0;
    }
    printf("%.2lf", res/100.00);
    return 0;
}

输入/输出：

4 11
8.02
7.43
4.57
5.39
2.00

跳转到最佳答案楼层

张育玮

很急！！！

傻眼貓咪

输出样例呢？

傻眼貓咪

你的题目不完整，样例的部分，需要作参考啊大哥

张育玮

傻眼貓咪 发表于 2021-10-31 19:05
你的题目不完整，样例的部分，需要作参考啊大哥

输入样例：

4 11
8.02
7.43
4.57
5.39
输出样例：

2.00

傻眼貓咪

代码：

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

int sort(const void * elem1, const void * elem2) // 定义函数：用于进行排序
{
    int f = *((int*)elem1);
    int s = *((int*)elem2);
    if (f > s) return  1;
    if (f < s) return -1;
    return 0;
}

int main()
{
    int N, K, sum = 0;
    double s;
    scanf("%d %d", &N, &K);
    int a[N];
    for(int i = 1; i <= N; i++)
    {
        scanf("%lf", &s);
        a[i] = s*100;
    }
    qsort(a, sizeof(a)/sizeof(*a), sizeof(*a), sort); // 排序
    int res = 0, r = a[N]/100*100+1;
    while(res+1 < r)
    {
        int mid = (res+r)/2;
        for(int i = 1; i <= N; i++) sum += a[i]/mid;
        if(sum >= K) res = mid;
        else r = mid;
        sum = 0;
    }
    printf("%.2lf", res/100.00);
    return 0;
}

输入/输出：

4 11
8.02
7.43
4.57
5.39
2.00