上海市计算机学会竞赛平台2023年11月月赛丙组推箱子
发布时间
阅读量：
阅读量
题目描述
小爱正在体验一款推箱子游戏。游戏每一关由长度为𝑛n的字符“”“”(空格)和“@”“@”(箱子)组成初始状态，让当前所有箱子集中到一块即可过关。
在一个动作中，如果目标移动的位置存在并且是空的，你可以将任何箱子向左移动一个位置或向右移动一个位置。当前所有箱子一排好，即任意两个箱子之间都不存在空格，方可进入下一关。
此款游戏共有𝑡t关，确定通过每一关卡所需的最小移动次数。
输入格式
第一行：一个整数𝑡t,表示𝑡t个关卡。
接下来是2𝑡2t行表示每一关初始情况。
一个整数𝑛n， 表示当前可用位置情况
一个长度为𝑛n的字符串，只包含“_”(空格)和(空格)和“@”$(箱子)
输出格式
输出共𝑡t行，每一行表示通过每一关卡所需的最小移动次数。
数据范围
- 对于 30%30%的数据，1≤𝑡≤10,1≤∑𝑛𝑖≤1031≤t≤10,1≤∑ni≤103。
- 对于 60%60%的数据，1≤𝑡≤103,1≤∑𝑛𝑖≤5∗1051≤t≤103,1≤∑ni≤5∗105。
- 对于 100%100%的数据，1≤𝑡≤104,1≤∑𝑛𝑖≤1061≤t≤104,1≤∑ni≤106。
样例数据
输入:
3
6
@@@__
3
@
10
@@__@@@
输出:
1
0
9
说明:
@@@___ (最右边箱子向左移动1个单位)
@ (移动0次)
3 + 4 + 1 + 1 = 9 。左边第2个箱子向右移动3个单位、最左边箱子向右移动4个单位、 右边第2个箱子向左移动1个单位、最右边箱子向左移动1个单位
详见代码:
#include <bits/stdc++.h>
using namespace std;
int t,n;
int main()
{
cin>>t;
while(t--)
{
string s;
int len;
cin>>len>>s;
vector<int> z(len);
vector<int> y(len);
for(int i=1;i<len;i++)
{
if (s[i-1]=='@')
{
z[i]=z[i-1]+1;
}
else
{
z[i]=z[i-1];
}
}
for(int i=len-2;i>=0;i--)
{
if (s[i+1]=='@')
{
y[i]=y[i+1]+1;
}
else
{
y[i]=y[i+1];
}
}
long long ans=0;
for(int i=0;i<len;i++)
{
if (s[i]=='_')
{
ans+=min(z[i],y[i]);
}
}
cout<<ans<<endl;
}
return 0;
}
全部评论 (0)
还没有任何评论哟~