CF990 E Post Lamps

CF990 E Post Lamps

[ 原题链接 ] http://codeforces.com/contest/990/problem/E

不同的区间长度 $$i$$ 的价格不同、需要的区间个数也不同，不满足二分或三分的特性，因此需要枚举 $$i$$。

在确定 $$i$$ 以后，pos 从 0 开始划分区间，区间必须覆盖 0 ~ n 的所有段（可以重复放）。

如果遇到 pos 不可以放灯，那么 pos 往回走到第一个可以放灯的位置。$$O(n)$$ 预处理上一个可以放灯的位置。

直到 pos 走到 n，或者遇到 pos+1 ~ pos+$$ i $$ 均不可放灯的情况，这样尽量往后放、少放灯的贪心是最优的。

而当 $$i$$ 小于最长连续一段不可放灯的长度时，最长的那段是无法覆盖全的。

因此进一步缩小了 $$i$$ 的枚举范围，经测试时限 $$4.5s$$ 可以 AC。

#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
    char ch=getchar(); int f=1; t=0;
    while ('0'>ch||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const int maxn=1000010;
int n,m,k,mx,cnt[maxn];
bool d[maxn];
ll s[maxn],ans=1LL<<60;
int main() {
    read(n); read(m); read(k);
    for (int i=1;i<=m;i++) {
        int x; read(x);
        d[x]=1;
    }
    if (d[0]) { printf("-1\n"); return 0; }
    for (int i=0;i<n;i++) {
        if (!d[i]) continue;
        cnt[i]=1; if (i) cnt[i]+=cnt[i-1];
        mx=max(mx,cnt[i]);
    }
    for (int i=1;i<=k;i++) read(s[i]);
    for (int i=mx;i<=k;i++) {
        int pos=0,cntcnt=0;
        while (pos<n) {
            if (d[pos]) {
                if (cnt[pos]==i) break;
                pos-=cnt[pos];
            } else {
                cntcnt++;
                pos+=i;
            }
        }
        if (pos>=n) ans=min(ans,s[i]*cntcnt);
    }
    if (ans>=1LL<<60) ans=-1;
    printf("%I64d\n",ans);
    return 0;
}