【时间复杂度】Codeforces990E Post Lamps

题意：

在一个区间[0,n]（注意是区间！）中，放入一些线段使得其能够覆盖所有位置。
放入线段的长度存在一个最大值$l_{max}$，对于每一个$l_x$，都有相应的花费。

放入线段的规则是，如果在第i处放入长为$l_x$线段，能够覆盖[i,i+$l_x$]。
有k个位置不能放。

并且只能使用同一种长度的线段。

求最小花费

分析：

这又是那个恶心的式子：
$\frac n 1+\frac n 2+\frac n 3+……+\frac n n$数量级约等于$nlogn$
然后暴力就可以了。。。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 1000020
using namespace std;
long long a[MAXN];
bool used[MAXN];
int near[MAXN];
int n,k,l,x;
int main(){int n;SF("%d%d%d",&n,&k,&l);for(int i=0;i<k;i++){SF("%d",&x);used[x]=1;}for(int i=1;i<n;i++){if(used[i]==0)near[i]=i;elsenear[i]=near[i-1];}for(int i=1;i<=l;i++)SF("%lld",&a[i]);long long ans=-1;if(used[0]==1){PF("-1");return 0;}int minle=1,cnt=0;for(int i=1;i<=n;i++){if(used[i]==1)cnt++;elsecnt=0;minle=max(minle,cnt+1);}for(int i=minle;i<=l;i++){int now=0;long long ans1=0;for(;now<n;now+=i,ans1+=a[i])now=near[now];if(ans1!=-1){if(ans==-1)ans=ans1;ans=min(ans,ans1);}}PF("%lld",ans);
}