[xdoj]1303jlz的刷题黑科技

先分析复杂度，给的数据是1e5的，那么我们至少需要一个nlogn的算法才可以。由于答案是一个数字，首先想到是二分法（一般答案是一个数字都可以通过二分法来完成）

下面是思路:

1.可以完成题目的条件是，每道题需要使用黑科技的次数一定要小于总的分钟数，计算每道题需要黑科技的次数这里要用到向上取证9/5=2，这里写了一个cal函数，比较方便实现，用强制转换ceil函数啥的有点麻烦，当然这个貌似是只能完成正整数的转换。

2.然后用二分查找，正常的二分查找是可以找到mid满足条件，且是唯一的mid。此题在二分区间内有多个值都可以满足条件，所以一定要遍历所有满足的元素，从中选取出最小的那一个作为结果输出出来，用x>y作为结束的条件。一开始时的时候是按注释那样写的，找到可以的一个值之后用while继续找比这个值小的结果，肯定会超时，因为相当于找到一个结果之后就开始一个一个找，退化的很严重，是一个非常智障的操作。

3.一开始想把二分写成从2开始，然后特殊判断了一大堆条件如注释写的那样，也是非常智障的操作，因为1与其他没有什么区别，x=y的情况也没有什么区别，不需要特殊处理

#include<bits/stdc++.h>

using namespace std;

#define maxn 100005

int a[maxn];

int m = ;

int cal(int x, int y)

{

    return (x + y - ) / y;

}

int merge(int x, int y, int n, int k)

{

    if (x >y)

        return ;

    int mid;

    mid = (x + y) / ;

    int sum;

    sum = ;

    int i;

    for (i = ; i < n; i++)

    {

        if (a[i]>mid)

        {

            sum += cal(a[i] - mid, k);

        }

    }

    if (sum < mid)

    {

        if (mid < m)

            m = mid;

        merge(x, mid - , n, k);

        /*    while (mid >= 2)

        {

        mid--;

        sum = 0;

        for (i = 0; i < n; i++)

        {

        if (a[i]>mid)

        {

        sum += cal(a[i] - mid, k);

        }

        }

        if (sum <= mid)

        m = mid;

        else

        break;

        }*/

    }

    else if (sum > mid)

    {

        merge(mid + , y, n, k);

    }

    else

    {

        m = mid;

        return ;

    }

}

int main()

{

    int t;

    scanf("%d", &t);

    while (t--)

    {

        int n;

        scanf("%d", &n);

        int i;

        for (i = ; i < n; i++)

            scanf("%d", &a[i]);

        int k;

        scanf("%d", &k);

        sort(a, a + n);

    /*    if (a[n - 1] == 1)

        {

            printf("1\n");

        }

        else if (a[n - 2] == 1 && (a[n - 1] - 1 - k <= 0))

            printf("1\n");

        else*/

            merge(, a[n - ] - k, n, k);

            printf("%d\n", m);

    }

}

巴特西

[xdoj]1303jlz的刷题黑科技

最新文章

热门文章