题解：AT_abc417_d [ABC417D] Takahashi's Expectation

· · 题解

听说正解是动态规划，其实这道题暴力能过...

好像 E 题过得比 D 题还多...

暴力思路

直接按照题目模拟，时间复杂度：O(NQ)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Info {
    int x,y,z;
} a[100010];
int n,x,t;
signed main(){
    scanf("%lld",&n);
    for (int i = 1;i <= n;i++) scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z);
    scanf("%lld",&t);
    while (t--){
        scanf("%lld",&x);;
        for (int i = 1;i <= n;i++) if (a[i].x >= x) x += a[i].y; else x -= a[i].z,x = max(x,0LL);
        printf("%lld\n",x);
    }
}

TLE 了 22 个点。

优化暴力

主播主播，我不想写动规，能不能在暴力上面改？

答案是有的，你直接在上面的代码中加一个特判：用 cnt 来记录所有 b_i 的和，如果每次询问的 x 严格大于 5000000，那就直接输出 x - cnt 即可。

主播主播，这是为什么？

我来解释一下。

这是因为，Atcoder 作为一个国际平台，其数据不容过水，所以，造数据肯定是造极限数据，而不是造水数据，所以，x 不是 10 ^ 9 就是 10 ^ 8，我们把大于 5000000 给特判了，剩下的数据还会多吗？这就是为什么暴力加优化就能过的原因。

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Info {
    int x,y,z;
} a[100010];
int n,x,t,cnt;
signed main(){
    scanf("%lld",&n);
    for (int i = 1;i <= n;i++) scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z),cnt += a[i].z;
    scanf("%lld",&t);
    while (t--){
        scanf("%lld",&x);
        if (x > 5000000){
            printf("%lld\n",x - cnt);
            continue;
        }
        for (int i = 1;i <= n;i++) if (a[i].x >= x) x += a[i].y; else x -= a[i].z,x = max(x,0LL);
        printf("%lld\n",x);
    }
}