题目链接:Attachments - 2016-2017 ACM-ICPC, South Pacific Regional Contest (SPPC 16) - Codeforces

结束前十分钟过题,就一个字,刺激

大致题意:道路上有有且只有没有拖车的四轮车(两轴)和一些带着一个两轮的拖车的四轮车(即存在三轴车和两轴车)

在道路某处设立压力测试点,记录下有轮子经过的时刻,两个相邻时刻差值小于等于1000说明是同一辆车的两对轮子经过,两个相邻时刻差值大于等于2000说明是两辆车的两对轮子经过。

给定一组数据,求有几辆有拖车和几辆没拖车的车子经过(如果多种结果输出Ambiguous,如无结果输出Impossible)

数组dp:dp[i]为在i位置能构成几辆四轮车

数组count:count[i]代表此处有几个解

代码如下

#include<bits/stdc++.h>

define inf 0x3f3f3f3f

using namespace std;
typedef long long LL;
int t;int n;
int a[300005], dp[300005], count[300005];
int main()
{

std::ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int n,y=1,mo=0,ji=1;
cin>>n;
for(int i=1;i<=n;i++)
    cin>>a[i]; 
memset(dp,-1,sizeof(dp));
dp[0]=0;
 a[0]=-inf;//防止i-1==0
sort(a+1,a+1+n);
a[n+1]=2*inf;//防止i+1>n
for(int i=2;i<=n;i++)
{
    if(dp[i-2]>=0&&a[i-1]-a[i-2]>1000&&a[i]-a[i-1]<2000&&a[i+1]-a[i]>1000)//i和i-1组成一辆车,此时i-1不能和i-2组成一辆车,i不能和i+1组成一辆车
    {
        count[i]=count[i-2];
        dp[i]=dp[i-2]+1;//四轮车++
    }
    if(i>=3&&dp[i-3]>=0&&a[i-2]-a[i-3]>1000&&a[i-1]-a[i-2]<2000&&a[i]-a[i-1]<2000&&a[i+1]-a[i]>1000)//i和i-1和i-2组成一辆车,此时i-2不能和i-3组成一辆车,i不能和i+1组成一辆车
    {
        count[i]=count[i-3];
        if(dp[i]>0)//存在两轮车
        {
            if(dp[i]!=dp[i-3])//相同说明唯一解
            {
                count[i]=1;
            }
        }
        else
        {
            dp[i]=dp[i-3];
            count[i]=count[i-3];
        }
    }
}
if (dp[n] == -1)
{
    cout<<"Impossible\n";
    return 0;
}
if (count[n] == 1)
{
    cout<<"Ambiguous\n";
    return 0;
}
cout<<"Cars without trailers: "<<dp[n]<<"\n";
cout<<"Cars with trailers: "<<(n - 2 * dp[n]) / 3<<"\n";
return 0;

}

————————————————
版权声明:本文为CSDN博主「yeah17981」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/yeah17981/article/details/116902062

Last modification:May 16, 2021
如果觉得我的文章对你有用,请随意投币