分治策略

棋盘覆盖 紫书

二分法
参考:http://blog.csdn.net/walkaway11/article/details/5930462

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e5+11;
const int INF = 0x3f3f3f3f;
int a[maxn],n,m;
bool C(int d){
    int last=0;//cow0
    for(int i = 1; i < m; i++){
        int cur=last+1;
        while(cur<n&&a[cur]-a[last]<d) cur++;
        if(cur==n) return 0;
        last=cur;
    }
    return 1;
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i = 0; i < n; i++){
            scanf("%d",&a[i]);    
        }
        sort(a,a+n);
        int l = 0, r = a[n-1]-a[0], mid, ans;
        for(int i = 0; i < 100; i++){
            mid = (l+r)>>1;
            if(C(mid)) l=mid+1;
            else r=mid-1;
        }
        printf("%d\n",r);
    }
    return 0;
}

UVA1121
二分法,总是分不清l r该怎么写
和以往的二分不同在于存在无解,只要输出时再判断一次即可

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+1e5+11;
const int INF = 0x3f3f3f3f;
typedef long long ll;
ll a[maxn];
ll n,s;
int C(int len){
    ll sum=0;
    for(int i = 1; i <= len; i++) sum+=a[i];
    if(sum>=s) return 1;
    for(int i = 1; i <= n-len; i++){
        sum-=a[i];sum+=a[i+len];
        if(sum>=s) return 1;
    }
    return 0;
}
int main(){
    while(scanf("%lld%lld",&n,&s)!=EOF){
        for(int i = 1; i <= n; i++) scanf("%lld",&a[i]);
        int l=1,r=n,mid;
        while(l<r){
            mid=(l+r)>>1;
            if(C(mid)) r=mid;
            else l=mid+1;
        }
        printf("%d\n",C(r)?r:0);
    }
    return 0;
}

https://www.zhihu.com/question/36132386
https://www.2cto.com/kf/201211/166043.html

标签: 算法, 学习

添加新评论