51nod 1402 最大值问题

1402 最大值 

题目来源： TopCoder

基准时间限制：1 秒 空间限制：131072 KB 分值: 20 难度：3级算法题

 收藏

 关注

一个N长的数组s[](注意这里的数组初始下标设为1，而不是0，即N个元素为s[1],s[2],...,s[N])，满足以下性质：

1）每个元素都是非负的整数，且s[1]=0；

2）任意两个相邻元素差值的绝对值不大于1，即| s[i]-s[i+1] |<=1；

3）对于部分特殊点xi，要求s[xi]<=ti（这样的特殊点一共M个）；

问在以上约束下s[]中的最大值最大可能是多少？

Input

多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=5
每组测试数据有相同的结构构成：
第一行两个整数N，M，表示s[]的长度与特殊点的个数，其中1<=N<=100000,0<=M<=50.
之后M行，每行两个整数xi与ti，其中1<=xi<=N,0<=ti<=100000，且xi以增序给出。
           

Output

每组数据一行输出，即数组的可能最大值。
           

Input示例

3
10 2
3 1
8 1
100000 0
2718 5
1 100000
30 100000
400 100000
1300 100000
2500 100000
           

Output示例

3
99999
2717
           

这道题    其实  每段的最大值就是   ans=（pos[i]-pos[i-1]-(num[i]-num[i-1])/2+num[i];

先找出每段的 绝对定位    num[i]=min(num[i],num[i-1]+pos[i]-pos[i-1]);   然后 这样其实就确定了特殊点的大小。但是不能保证绝对的接近，所以要从右往左扫一遍，然后

ans=（pos[i]-pos[i-1]-(num[i]-num[i-1])/2+num[i],把ans用数组记录一下，最好用原数组，要不要还要把m项赋值一下

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<math.h>
#define inf 0x3f3f3f3f
using namespace std;
int flag;
int n,m;
struct node {
    int pos;
    int num;
}b[1000005];
int a[100005];
int main()
{
   int t;
   scanf("%d",&t);
   while(t--)
   {
       flag=-1;
       scanf("%d%d",&n,&m);
       if(m==0)
       {
           printf("%d\n",n-1);
            continue;
       }
       for(int i=1;i<=m;i++)
       {
           scanf("%d%d",&b[i].pos,&b[i].num);
       }
       b[0].pos=1,b[0].num=0;
        for(int i=1;i<=m;i++)
            b[i].num=min(b[i].num,b[i-1].num+b[i].pos-b[i-1].pos);
        for(int i=m;i>=1;i--)
       {
           if(b[i-1].num>b[i].num) b[i-1].num=min(b[i-1].num,b[i].num+b[i].pos-b[i-1].pos);
       }
       for(int i=1;i<=m;i++)
       {
            b[i-1].num=(b[i].pos-b[i-1].pos+b[i].num+b[i-1].num)/2;
       }
       int maxx=-1;
       for(int i=0;i<=m;i++)
       {
           maxx=max(maxx,b[i].num);
           maxx=max(maxx,b[m].num+n-b[m].pos);
       }

        printf("%d\n",maxx);
   }

    return 0;
}