当前位置:首页 > 资讯 > info5 > 正文

POJ 3258 River Hopscotch (二分)

发表于: 2015-01-23   作者:u013013910   来源:转载   浏览:
摘要: 题目地址:POJ3258水题。二分距离,判断是否可行。需要注意的是最后一个,因为最后一个是没法移除的,所以还要倒着判断一下。代码如下:#include #include #include #include #include #include #include #include #include usingnamespacestd; #defineLL__int64 #definepiacos(-1

题目地址:POJ 3258

水题。二分距离,判断是否可行。需要注意的是最后一个,因为最后一个是没法移除的,所以还要倒着判断一下。

代码如下:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=9901;
const int INF=0x3f3f3f3f;
const double eqs=1e-8;
int a[51000], vis[51000];
int bin_search(int n, int m)
{
        int low=0, high=1e9, mid, ans, cnt, last;
        while(low<=high) {
                mid=low+high>>1;
                int flag=0;
                cnt=0;
                last=0;
                memset(vis,0,sizeof(vis));
                for(int i=0; i<n; i++) {
                        if(a[i]-last<mid) {
                                cnt++;
                                if(cnt>m)
                                        break;
                        } else {
                                last=a[i];
                                vis[i]=1;
                        }
                }
                for(int i=n-1;i>=0;i--){
                        if(vis[i]){
                                if(a[n]-vis[i]<mid){
                                        cnt++;
                                        if(cnt>m) break;
                                }
                                else break;
                        }
                }
                if(cnt>m) high=mid-1;
                else{
                        ans=mid;
                        low=mid+1;
                }
        }
        return ans;
}
int main()
{
        int lenth, i, n, m, ans;
        scanf("%d%d%d",&lenth,&n,&m);
        for(i=0; i<n; i++) {
                scanf("%d",&a[i]);
        }
        if(!n) {
                printf("%d\n",lenth);
                return 0;
        }
        sort(a,a+n);
        a[n]=lenth;
        ans=bin_search(n,m);
        printf("%d\n",ans);
        return 0;
}


POJ 3258 River Hopscotch (二分)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
分析:题意 源岸数量<=3 很好判断 3:num[0]+num[1]+num[2] 2:num[1] ,1:num[0] 源岸数量>3 #i
题目:http://poj.org/problem?id=1700 Crossing River Time Limit: 1000MS Memory Limit: 10000K T
1143: [CTSC2008]祭祀river Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2026 Solved: 1017 [
K Best Time Limit: 8000MS Memory Limit: 65536K Total Submissions: 6419 Accepted: 1712 Case Ti
Garland Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 1184 Accepted: 515 Descrip
题意:在平面内给出n个点,问你这些点一共能组成几个不相等的正方形? 思路:几何 + 二分。先排序,
Garland Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 1438 Accepted: 638 Descrip
Squares Time Limit: 3500MS Memory Limit: 65536K Total Submissions: 17554 Accepted: 6678 Descr
Description My birthday is coming up and traditionally I'm serving pie. Not just one pie, no,
Pie Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 14107 Accepted: 4837 Special J
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号