ACM模版

描述

题解

一开始看到这道题，感觉挺简单的，但是，我只关注了明沟，却忽略了暗坑！！！
首先，这里我们将这些特殊点成为卡点，但是不是所有的卡点都能卡住数据的，其中，最容易想到的是t < x - 1的点是无法卡住数据的，所以我们可以直接忽略掉，那么剩下的卡点一定是可以卡住数据的，但是这时候筛选出来的卡点其中有两种情况并无法精准的卡住数据，即：

T[i] > T[i - 1] + X[i] - X[i - 1]
T[i] > T[i + 1] + X[i + 1] - X[i]

所以我们需要对这两种情况进行精度校正，这时，需要强调的是，当第二种情况出现时，我们有可能需要对前边已经校正过精度的点重新校正一下，因为第i个如果因为第i + 1个而改变，那么第i - 1个就存在因为第i个而改变的可能。

代码

#include <iostream>

using namespace std;

const int MAXM = 55;

int X[MAXM];
int T[MAXM];

int main(int argc, const char * argv[])
{
// freopen("/Users/zyj/Desktop/input.txt", "r", stdin);

    int P;
    cin >> P;

    int N, M;
    int x, t;
    while (P--)
    {
        cin >> N >> M;
        int key = 0;
        for (int i = 0; i < M; i++)
        {
            cin >> x >> t;
            if (t < x - 1)  // 会卡住数据上限的转存
            {
                X[key] = x;
                T[key++] = t;
            }
        }
        // 如理特殊卡点 ex: (3)*(0) (3)无法取3
        for (int i = 0; i < key; i++)
        {
            if (T[i] > T[i - 1] + X[i] - X[i - 1] && i != 0)
            {
                T[i] = T[i - 1] + X[i] - X[i - 1];
            }
            if (T[i] > T[i + 1] + X[i + 1] - X[i] && i != key - 1)
            {
                T[i] = T[i + 1] + X[ i + 1] - X[i];
                if (i >= 2)
                {
                    i -= 2;
                }
            }
        }

        if (!key)
        {
            cout << N - 1 << '\n';
            continue;
        }
        int ans = T[0] > (X[0] + T[0] - 1) / 2 ? T[0] : (X[0] + T[0] - 1) / 2;
        for (int i = 1; i < key - 1; i++)
        {
            if ((T[i] + T[i + 1] + X[i + 1] - X[i]) / 2 > ans)
            {
                ans = (T[i] + T[i + 1] + X[i + 1] - X[i]) / 2;
            }
        }
        ans = T[key - 1] + N - X[key - 1] > ans ? T[key - 1] + N - X[key - 1] : ans;
        cout << ans << '\n';
    }

    return 0;
}