二分-2020-05-09

记录今天做的两道二分题

1.牛牛的揠苗助长

题目链接：https://ac.nowcoder.com/acm/contest/5531/C
题目：
牛牛有一块长度大小为n的菜园，他首先对这块菜园从1到n进行了编号，每一块地分别为1号、2号...n号菜地，然后他往每块菜地中都种下了一些水稻，一开始，第i块菜地中的水稻高度均为a[i]个单位。然后我们知道水稻的生长周期都是n天，也就是说每逢n天水稻就会长高一个单位。但是不巧的是整个菜园中每一块菜地的生长周期都错开了，具体来说，第1天的时候第1块菜地中的水稻长高一个单位，第2天的时候第2块菜地中的水稻长高一个单位....第n天的时候第n块菜地中的水稻长高一个单位，接下来第n+1天，又轮到第1块菜地中的水稻长高一个单位以此类推。

每天在水稻进行自然生长之后，牛牛可以施展他神奇的魔法，这个魔法可以让任意一块菜地中的水稻长高一个单位，或者让任意一块菜地中的水稻缩短一个单位，当然啦，他也可以不进行任何操作。

牛牛看到菜园中的水稻参差不齐十分难受，请问至少在第几天，他能够让所有的水稻都长到同一个高度？

输入：

第一行是一个正整数n，，表示有菜园有n块菜地。
接下来一行输入n个正整数，表示每块菜地上水稻的高度，水稻的高度
保证一开始输入时水稻的高度不全都相同（数据保证答案至少为1）。

中位数的一个性质，如果一个数列中的数全部放到数轴上，那么到这些数距离之和最小的数是中位数。
从题意来看，如果天数给得足够大，我们肯定可以使所有水稻高度一致，所以我们可以二分天数，在check函数中，我们可以先让这些水稻自然生长，然后对这些水稻进行操作使其高度全部相同(这里，将标准设置为数列的中位数，高于中位数的，缩短它，低于中位数的，长高)，如果操作数小于天数，则返回true

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 1e5+100;

int n;
LL a[N],b[N];

bool check(LL d){
   //d天，先自然生长，然后操作，使水稻高度全部一致的操作次数如果小于等于d，说明d天满足条件
    for(int i = 1; i<=n; i++){
        b[i] = a[i] + (d%n>=i);
    }
    sort(b+1,b+1+n);
    //在一个数列(放在数轴中)中，中位数距离所有点的距离之和最小
    LL ans = 0;
    LL mid = b[(n+1)/2];
    for(int i = 1; i<=n; i++) ans += abs(b[i] - mid);
    return ans <= d;
}
int main()
{
    scanf("%d",&n);
    
    for(int i = 1; i<=n; i++) scanf("%d",&a[i]);
    
    LL l = 0, r = 1e15;
    while(l<r){
        LL mid = (l+r)>>1;
        if(check(mid)) r = mid;
        else l = mid+1;
    }
    printf("%lld\n",l);
    return 0;
}

J.签到题

题目链接：https://ac.nowcoder.com/acm/contest/3007/J
现有一个边长为正整数的三角形，问能否以其三个顶点为圆心画三个圆，使三个圆两两外切，三边长均不超过
输入描述:
三个正整数，表示三角形的边长
输出描述:
如果三条边不能构成三角形，输出“wtnl”
如果三条边能构成三角形但不能画出符合要求的圆，输出“No”
否则输出一行“Yes”
然后在第二行输出一组方案，按升序给出三个圆的半径，保留两位小数

不满足三角的定义，输出wtnl，否则二分最小的那个圆的半径，一个半径确定，其他两个圆得半径也就确定了，如果可以放到三角形的三个点上，那就满足条件。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int a[3];

int main()
{
    cin>>a[0]>>a[1]>>a[2];
    sort(a,a+3);
    if(a[0] + a[1] <= a[2]|| a[2] - a[1] >= a[0]) {
        cout<<"wtnl"<<endl;
        return 0;
    }
    double x = a[0]*1.0,y = a[1]*1.0,z = a[2]*1.0;
    
    double l = 0, r = x;
    while(r-l>1e-4){
        double mid = (l+r)/2;
        if((x+y-2*mid)>=z) l = mid;
        else r = mid;
    }
    if(x+y-2*l -z>1e-4) cout<<"No"<<endl;
    else {
        double b[3] = {l,x-l,y-l};
        sort(b,b+3);
        cout<<"Yes"<<endl;
        printf("%.2lf %.2lf %.2lf\n",b[0],b[1],b[2]);
    }
    return 0;
}