AT_ddcc2019_final_a题解

· · 题解

传送门：AT_ddcc2019_final_a

切入正题

思路

这道题其实就是一道大模拟再加一丢丢贪心。

通过一个雪方块的时间为 1 秒，通过一个冰方块的时间为 \frac{1}{k+2} 秒。（k 为这个冰方块前连续的冰方块数量）

其实不难发现，如果想要在把 1 个雪方块变成冰方块之后所用时间最少，就需要将这个方块添加在最长的连续的冰方块之后。

所以，我们可以先计算出来最长的连续的冰方块数量，以及再改变前的所需的时间，然后就可以得出在更改之后最少时间为：

现在所需时间减 1（更改前通过雪方块的时间）加 \frac{1}{k+2}（更改后通过冰方块的时间，此处假设最长联通冰方块数量为 k）

代码

#include<bits/stdc++.h>
using namespace std;
double n,cnt,cnt2,k,ans;//n为总方块数量，cnt为统计连续冰方块数，cnt2为最长连续冰方块数，k为计算现在所需时间的统计值，ans为最终答案 
char a[100005];//开一个字符类型数组a存储滑雪道 
int main() {
    std::ios::sync_with_stdio(false);//关闭cin，cout同步流，可提速，萌新初学者可忽略 
    cin>>n;//输入总方块数 

    //计算最长连续冰方块数

    for(int i=1;i<=n;i++){//循环输入冰雪方块 

        cin>>a[i];//输入冰雪方块 
        if(a[i]=='>'){
            cnt++;//统计当前连续冰方块数量 
            cnt2=max(cnt2,cnt);//不断更新最长连续冰方块数
        }
        else    cnt=0;//如果当前方块不为冰方块（'>'）时，停止统计。 
    }

    //计算现在所需时间 

    for(int i=1;i<=n;i++){
        if(a[i]=='>'){
            ans+=1/(k+2);//增加通过当前冰方块所需时间 
            k++;//增加联通冰块值 
        }
        else{
            k=0;//如果当前方块不为冰方块（'>'）时，停止统计。 
            ans++; //增加通过当前雪方块时间 
        }
    }
    cout<<setprecision(15)<<ans-1+1/(cnt2+2);//输出最后答案 
    return 0;
}
//问题解决~~

AC记录

审核员大大最好了，让孩砸过吧qwq