CF1690C Restoring the Duration of Tasks

Coros_Trusds · 2022-06-08 06:37:03 · 题解

题目分析

注意到题目中保证 s,f 均严格单调递增。所以对于当前一个任务 i，他可能的完成时间为 f[i]-s[i]，但我们发现 s[i]\lt f[i-1] 时，完成时间不是 f[i]-s[i]，而是 f[i]-f[i-1]。

综上，每个答案为 f[i]-\max\{s[i],f[i-1]\}。

代码

// Problem: C. Restoring the Duration of Tasks
// Contest: Codeforces - Codeforces Round #797 (Div. 3)
// URL: https://codeforces.com/contest/1690/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Date:2022-06-07 23:01
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>
#include <climits>//need "INT_MAX","INT_MIN"
#include <cstring>//need "memset"
#include <numeric>
#include <algorithm>
#include <cmath>
#include <queue>
#define enter putchar(10)
#define debug(c,que) std::cerr << #c << " = " << c << que
#define cek(c) puts(c)
#define blow(arr,st,ed,w) for(register int i = (st);i <= (ed); ++ i) std::cout << arr[i] << w;
#define speed_up() std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
#define mst(a,k) memset(a,k,sizeof(a))
#define stop return(0)
const int mod = 1e9 + 7;
inline int MOD(int x) {
    if(x < 0) x += mod;
    return x % mod;
}
namespace Newstd {
    inline int read() {
        int ret = 0,f = 0;char ch = getchar();
        while (!isdigit(ch)) {
            if(ch == '-') f = 1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            ret = (ret << 3) + (ret << 1) + ch - 48;
            ch = getchar();
        }
        return f ? -ret : ret;
    }
    inline double double_read() {
        long long ret = 0,w = 1,aft = 0,dot = 0,num = 0;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') w = -1;
            ch = getchar();
        }
        while (isdigit(ch) || ch == '.') {
            if (ch == '.') {
                dot = 1;
            } else if (dot == 0) {
                ret = (ret << 3) + (ret << 1) + ch - 48;
            } else {
                aft = (aft << 3) + (aft << 1) + ch - '0';
                num ++;
            }
            ch = getchar();
        }
        return (pow(0.1,num) * aft + ret) * w;
    }
    inline void write(int x) {
        if(x < 0) {
            putchar('-');
            x = -x;
        }
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace Newstd;

const int N = 2e5 + 5;
int st[N],ed[N];
int T,n;
inline void solve() {
    n = read();
    for (register int i = 1;i <= n; ++ i) st[i] = read();
    for (register int i = 1;i <= n; ++ i) ed[i] = read();
    for (register int i = 1;i <= n; ++ i) {
        printf("%d ",ed[i] - std::max(st[i],ed[i - 1]));
    }
    puts("");
}
int main(void) {
    T = read();
    while (T --) {
        solve();
    }

    return 0;
}