1402 最大值 题目来源： TopCoder 基准时间限制：1 秒 空间限制：131072 KB 分值: 20 难度：3级算法题 收藏 关注 一个N长的数组s，满足以下性质： 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 题解：找到每一个临界点，做一条斜率为1和-1的直线，对比取最小
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define M 100010 int a[M]; int main() { int n, m, xi, ti, temp, t; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) { a[i] = i-1; } for(int i=0; i<m; i++) { scanf("%d%d", &xi, &ti); temp = xi; while(temp <= n) { if(temp-xi+ti < a[temp]) { a[temp] = temp-xi+ti; } temp++; } temp = xi; while(temp >= 1) { if(xi-temp+ti < a[temp]) { a[temp] = xi-temp+ti; } temp--; } } int ans = 0; for(int i=1; i<=n; i++) { ans = max(ans, a[i]); } printf("%d\n", ans); } return 0; }