最近回顾之前的比赛的时候发现了这一题,由于之前一直在刷dp类型的题目,导致我没有读题的时候认为这题是个dp类型的题目,但是我发现我找不到状态方程,果断放弃了这个想法...
之后我发现这一题根本不需要任何算法,相当于一个模拟过程了,我的思路是一条路走到死(开始向左或者向右一直走,设置两个指针li与ri来保存左右的目前的位置,如果此时的水滴数量大于等于10,则就把对应的指针进行的往左或者右的运动,最开做的时候忽略了很多东西,包括完成水滴合并的时候剩余向左或向右水滴的数量,之后才整理出ls=a[li]+ls-9,脑子不够聪明。 我还有一点错误是判断temp==2的时候忽略了此时左边或者右边的水滴以及合并完并且释放,导致了只有80%的通过率,出去溜了一圈之后恍然大悟哈哈哈。判断了一下此时是否两边存在水滴合并完毕的情况,那么可能有人问了,会不会出现li==-1&&ri==n的情况?答案是不可能的,如果这样的话就直接跳出循环了(大概吧...)
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n,p;
cin>>n>>p;
vector<int> a(n);
for(int i=0;i<n;i++)
cin>>a[i];
if(a[p-1]!=9)
{
cout<<"0 0"<<endl;
return ;
}//当目前的水滴不是9的情况直接跳出,我这里忽略10了但是问题不大
int ls=1,rs=1,li=p-2,ri=p,temp=0;//ls与rs是当前左右游离水滴的数量,ri与li是两边的指针
bool isl=1;//设置了一个bool类型的判断下一步的方向,其实类似于一个递归了,可以稍微简化一下写俩函数,但是我懒了...
while(li!=-1||ri!=n)//这里是或,不能为且
{
if(isl)//向左边计算
{
if(a[li]+ls>=10&&li!=-1)
{
ls=a[li]+ls-9;
rs++;
isl=0;
temp=0;
li--;
}
else
{
isl=0;
temp++;
}
}
else//向右边计算
{
if(a[ri]+rs>=10&&ri!=n)
{
rs=a[ri]+rs-9;
ls++;
isl=1;
temp=0;
ri++;
}
else
{
isl=1;
temp++;
}
}
if(temp==2)//如何没有将temp重置,那么说明此时既不能往左也不能往右
{
if(li==-1&&ri!=n)//如果左边合并完毕
cout<<ls<<" 0"<<endl;
else if(ri==n&&li!=-1)//如果右边合并完毕
cout<<"0 "<<rs<<endl;
else//如果两边都没有合并完毕
cout<<"0 0"<<endl;
return ;
}
}
cout<<ls<<" "<<rs<<endl;
}
signed main(void)
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
**欢迎各路大佬hack我