codeforces 617 C. Tourist's Notes (二分)

Posted by 111qqz on Wednesday, March 30, 2016

TOC

题目链接 题意:有n天的旅行,但是只剩下了m天的旅行记录,记录格式为d[i],h[d[i]],表示第i个记录是第d[i]天的,高度为h[d[i]],相邻两天的高度之差的绝对值不超过1.问满足以上条件的最大的h是多少。无解输出impossible. 思路:为了练习二分。 二分高度,然后check是否合法。注意边界,所以可以添加两个点。

/* ***********************************************
Author :111qqz
Created Time :2016年03月30日 星期三 16时53分57秒
File Name :code/cf/problem/538C.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
const int M=1E9; //上界并不是h的最大值。。因为还可以继续往上走啊。。
int n,m;
int h[N],d[N];



bool check (int x)
{
  //  cout<<"x:"<<x<<endl;
    
    for ( int i = 1 ; i <= m-1 ; i++)
    {
    if (x<h[i]||x<h[i+1]) return  true;
    int cost = abs(x-h[i]) + abs(h[i+1]-x);
//	cout<<"cost:"<<cost<<endl;
    if (cost<=d[i+1]-d[i]) return  true;
    }
    return false;
}
int bin()
{
    int l = 0 ;
    int r = M ;
    int mid;
    while (l<=r)
    {
    mid = (l+r)/2;
    if (check(mid))
        l = mid + 1;
    else r = mid -1;
    }
    if (r>M) return -1;
    return r;
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif

    cin>>n>>m;
    m++;
    for ( int i = 2 ; i <= m ; i++) cin>>d[i]>>h[i];
	
    d[1] = 1;
    h[1] = h[2] + abs(d[2]-1);   //为了处理端点,于是增加两个点。
    m++;
    d[m] = n;
    h[m] = h[m-1] + abs(n-d[m-1]);
	

    for ( int i = 1 ; i <= m-1 ; i++)
    {
        int tmp = abs(h[i+1]-h[i]);
        if (d[i+1]-d[i]<tmp)
        {
        puts("IMPOSSIBLE");
        return 0;
        }
    }
    int ans = bin();
    if (ans==-1)
    {
        puts("IMPOSSIBLE");
    }
    else
    cout<<ans<<endl;

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付