函数模拟 Atcoder 082 F Sandglass

原题：Sandglass

原题大意

给一个沙漏，一半叫A，另一边叫B，初始A在上B在下，A+B的沙子一共为X，每秒钟走一滴沙，再给出k个时刻，每个时刻都将沙漏倒置，现在有Q个询问，每个询问（t，a）代表若起始A中有a滴沙，t时刻时A中还有多少沙子，每个询问的时刻t是递增的给出。

算法分析

ft(x)表示若A中初始沙数量为x，在t时刻A中剩余的沙的数量。举几个例子之后会发现，ft(x)的函数都是这样的

（x前面的斜率也可以为-1），同时函数上限不会超过X，下限不会低于0，模拟即可

程序代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int X, K, Q, r[maxn], t[maxn], a[maxn], ub, lb, b, t1, t2, add, tmp, diff, sgn;
void Add(int &n, int num){
    n+=num;
    n = max(0, min(X, n));
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> X >> K;
    for(int i = 1; i <= K; i++) cin >> r[i];
    cin >> Q;
    for(int i = 1; i <= Q; i++) cin >> t[i] >> a[i];
    t1 = 0, t2 = 1;
    lb = b = 0, ub = X, sgn = -1;
    while(t2 <= Q){
        if(t[t2] > r[t1+1] && t1 < K){
            t1++;
            add = sgn*(r[t1] - r[t1-1]);
            Add(lb, add); Add(ub, add);
            b+=add;
            sgn*=-1;
        }
        else{
            diff = (t[t2] - r[t1]);
            tmp = max(lb, min(ub, a[t2]+b));
            Add(tmp, diff*sgn);
            cout << tmp << "\n";
            t2++;
        }
    }
    return 0;
}