链接:

题意:

度度熊在玩一个好玩的游戏。

游戏的主人公站在一根数轴上，他可以在数轴上任意移动，对于每次移动，他可以选择往左或往右走一格或两格。

现在他要依次完成 n 个任务，对于任务 i，只要他处于区间 [ai,bi] 上，就算完成了任务。

度度熊想知道，为了完成所有的任务，最少需要移动多少次？

度度熊可以任意选择初始位置。

思路:

刚开始以为是贪心,按y拍了个序,疯狂wa,找了个题解发现是要按顺序.....

维护当前所在区间,然后找从最近的跑来跑去就行.

代码:

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e3+10;

struct Node

{

    int x, y;

}node[MAXN];

int n;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    int t;

    cin >> t;

    while (t--)

    {

        cin >> n;

        for (int i = 1;i <= n;i++)

            cin >> node[i].x >> node[i].y;

        int res = 0;

        int l = node[1].x, r = node[1].y;

        for (int i = 2;i <= n;i++)

        {

            if (node[i].x >= l && node[i].y <= r)

                l = node[i].x, r = node[i].y;

            else if (node[i].x >= l && node[i].x <= r && node[i].y > r)

                l = node[i].x;

            else if (node[i].x < l && node[i].y >= l && node[i].y <= r)

                r = node[i].y;

            else if (node[i].x > r)

            {

                res += (node[i].x-r+1)/2;

                l = node[i].x, r += ((node[i].x-r+1)/2)*2;

                r = min(r, node[i].y);

            }

            else if (node[i].y < l)

            {

                res += (l-node[i].y+1)/2;

                r = node[i].y, l -= ((l-node[i].y+1)/2)*2;

                l = max(l, node[i].x);

            }

        }

        cout << res << endl;

    }

    return 0;

}

巴特西

HDU-6669-Game(模拟,贪心)

链接:

题意:

思路:

代码:

最新文章

热门文章