题解：P12648 [KOI 2024 Round 2] 路灯

· · 题解

P12648 [KOI 2024 Round 2] 路灯

题目在这里

哇，这题差点搞死我啊，卡了我好好好久。

Solution

其实本题看似复杂其实一点也不复杂，看似要用各种各样的离奇优化方式，其实就是一道暴力题，只要做法想出来了就直接暴力即可。

看到这种看似要给每个位置遍历一遍的题目，一定要往另一个方向去想。

既然不可以遍历位置，那我们可以遍历到路灯的距离。

首先，路灯所在地的黑暗程度绝对为 0，废话。

for(int i=1;i<=min(k,n);i++) cout<<"0\n";
k-=n;

然后枚举是否可以与路灯 j 距离为 i 处形成一个点使这个点未被遍历过且在 j 与 j+1，j 与 j-1 之间，如果成立，输出即可，否则继续。

代码也十分简单。

for(int i=1;i<=l;i++){
    for(int j=1;j<=n;j++){
        if(a[j]-a[j-1]>i&&f.find(a[j]-i)==f.end()) 
            cout<<i<<"\n",k--,f[a[j]-i]=1;
        if(!k) return 0;
        if(a[j+1]-a[j]>i&&f.find(a[j]+i)==f.end()) 
            cout<<i<<"\n",k--,f[a[j]+i]=1;
        if(!k) return 0;
    }
}

注意，要将位置 -1 与位置 L+1 也当作有一个路灯来框定范围，并且这两个位置不用加入上述处理。

代码。

#include<iostream>
#include<cmath>
#include<algorithm>
#include<map>
#define int long long
using namespace std;
const int N=405000;
int n,l,k,a[N],s;
map<int,int> f;
signed main(){
    cin>>l>>n>>k;
    a[0]=-1;
    a[n+1]=l+1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=min(k,n);i++) cout<<"0\n";
    k-=n; 
    if(k<=0) return 0;
    for(int i=1;i<=l;i++){
        for(int j=1;j<=n;j++){
            if(a[j]-a[j-1]>i&&f.find(a[j]-i)==f.end()) 
                cout<<i<<"\n",k--,f[a[j]-i]=1;
            if(!k) return 0;
            if(a[j+1]-a[j]>i&&f.find(a[j]+i)==f.end()) 
                cout<<i<<"\n",k--,f[a[j]+i]=1;
            if(!k) return 0;
        }
    }
    return 0;
}

证明

为什么这个时间复杂度可以通过。

最优复杂度 O(k)。

看似这个方法在一些特殊情况下可能会出现极坏复杂度。如全部路灯挤在一起或每两个之间只相差一个距离时，可能会让它多次从遍历已经没有可以出现点的路灯。但是假设在一种情况中，一共有 n 个路灯，两两距离为 1。k 极大，为 1\times 10^{5} 时。在处理完距离为 0 与距离为 1 的以后，一共运行了 2n 次，那么剩下的输出次数为 k-2n 次。若它剩余每一次都要运行至最后一个路灯时才出现符合条件的情况时，情况最坏。往坏里算要运行 n(k-2n)=nk-2n^{2} 次。所以不管 n 是大是小，运行次数都不大，可以稳稳通过此题。

记录在这里。

最后，最最最重要的一点，你们知道我为什么卡了这么久吗。

那我问你，十年 OI 一场空，下一句是什么？