题解 | #糖糖别胡说,我真的不是签到题目#

糖糖别胡说,我真的不是签到题目

https://ac.nowcoder.com/acm/problem/14583

稍有常识的人都看得出,这里用的到前缀和差分,然后要倒着做,然后粗略的想到了要找前一个比后一个大的,但是因为时间问题,睡觉了,没有总结出上升序列,也没有看到分01两个序列,然后我就卡在倒着做那里了。 然后吐槽一下题目排版(排版全责,输入压成一行,针不戳)
和队友交流了以后,队友完全不能理解我犯得弱智错误,不知道我的问题在哪里(悲)
//我菜死了,浇浇我。
然后总结一下问题吧:
首先,长期缺乏有强度的训练和复习,前缀和差分忘了怎么做了。
其次,做题的时间再晚上,思维运转速度过慢,题目没有完全理解。

还是要多思考,不能养成看题解的坏习惯,这对思维的锻炼是有百害无一利的。
以下是ac代码:

#include <bits/stdc++.h>

using namespace std;
const int N = 5e4 + 5;
long long a[N], b[N];
int main()
{

    int t;
    cin >> t;
    while (t--)
    {

        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i] >> b[i];
        }
        for (int i = n; i >= 1; i--)
        {
            b[i] -= b[i - 1];
        }
        for (int i = 1; i <= m; i++)
        {
            int x;
            cin >> x;
            b[1]++;
            b[x + 1]--;
        }
        for (int i = 1; i <= n; i++)
        {
            b[i] += b[i - 1];
           // cout << a[i] << " " << b[i] << "\n";
        }
        //cout << "\n";
        int m0 = 0, m1 = 0, ans = 0;
        for (int i = n; i >= 1; i--)
        {
            if (a[i] == 0)
            {
                if (b[i] >= m1)
                {
                    ans++;
                }
                if (b[i] > m0)
                    m0 = b[i];
            }
            else
            {
                if (b[i] >= m0)
                {
                    ans++;
                }
                if (b[i] > m1)
                    m1 = b[i];
            }
        }
        cout << ans << "\n";
    }

    return 0;
}
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务