CF1649A Game题解

__vector__ · 2022-03-10 21:07:28 · 题解

题目大意：

有 n 个格子，编号从 1 到 n。给定一个长度为 n 的序列 a，若 a_i = 1，代表第 i 个格子是陆地，若 a_i = 0，代表第 i 个格子有水。
你初始在第 1 个格子，你要走到第 n 个格子。路程中不能走在有水的格子上。
如果路中遇到了有水的格子，那么你需要花费硬币跳过去。假设你现在在 pos1，你要跳到 pos2，那么就要花费 pos2-pos1 个硬币。你只能使用一次硬币。
问最少需要多少个硬币才能走到第 n 个格子，保证有解。

题目解法：

直接遍历一遍数组 a，用变量 pos1 记录第一个有水的格子，用变量 pos2 记录最后一个有水的格子。最后答案就是 pos2-pos1+2。
注：
要注意特判没有一个格子有水的情况，这种情况输出 0 即可。

AC 代码：

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=105;
    int t;
    int n;
    int a[maxn];
    void main()
    {
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            int ans=0;
            int pos1=0,pos2=0;
            bool flag=1,flag2=1;
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
                if(!a[i]&&flag)
                {
                    flag=0;
                    pos1=i;
                }
            }
            for(int i=n;i>=1;i--)
            {
                if(!a[i]&&flag2)
                {
                    flag2=0;
                    pos2=i;
                }
            }
            if(!pos1&&!pos2)
            {
                printf("0\n");
            }
            else printf("%d\n",(pos2-pos1+2));
        }
    }
}
int main()
{
    Main::main();
    return 0;
}