虽然只是10^6的数据量，但用cin会tle。一直知道cin常数大，但没想到会是10^2这个级别。

我们枚举每个power的lamp，然后对每个power用平均logn的代价去求它的cost，最后取最小值

对于每个power，我们从左往右地去照亮整个区间，首先0点要插一个路灯，下一个路灯理想上想插在0+power的位置（这样区间不被重复照亮），但实际上power位置上的路灯可能被blocked了，所以我们想在power位置之前的离power最近的一个位置安装路灯。如果发现最近的那个位置离power的位置大于power了，那power位置永远不会被照亮，返回-1

这样贪心实际上每次算cost的代价是 n/power，为什么平均意义下是logn的呢。

因为整体下来是n/1+n/2+n/3+n/4+...+n/k，可见k越大整体复杂度越高，我们考虑其上限及k=n的情况，得到n(1+1/2+1/3+1/4+...+1/n)，而1+1/2+1/3+1/4+1/5+...+1/n这个数列求和是logn级别的因为可以把1/3+1/4看成1/2，1/5+1/6+1/7+1/8看成1/2，接下来的每8项，16项都是1/2。然后把n看成2^k的话也可以把n看成2^0+2^1+2^2+...+2^k-1，其中每一份都对数列的和贡献出1/2，所以这个数列求和是1/2*logn左右，及logn级别的。

1 #include
     
       2 using namespace std; 3  4 int n,m,k;//长度为n，m个 5 int cost[1000005],blocked[1000005],last_unblocked[1000005]; 6 long long ans; 7 int main() 8 {     9     cin>>n>>m>>k;10     for(int i=1;i<=m;i++){11         int x; scanf("%d",&x);12         blocked[x]=1;13     }14     for(int i=1;i<=k;i++) scanf("%d",&cost[i]); //power为i的lamp花费cost[i] 15     if(blocked[0]) { cout<<-1; return 0; }16     17     int last=0;18     for(int i=1;i<=n;i++){19         if(!blocked[i]) last=i;20         last_unblocked[i]=last;21     }22     for(int i=1;i<=k;i++){
   //模拟用每个power的路灯 23         long long c=0;24         for(int index=0;index
      
       =n) index=n;27             else{28                 int loc=last_unblocked[index+i];//下一个路灯想插在index+i，但这里可能被blocked了，那想照亮这个地方就找这个位置前面最近能放路灯的位置29                 if(loc<=index) { c=-1; break; }30                 index=loc;31             }32         }33         if(c==-1) continue;34         else{35             if(ans==0) ans=c;36             else ans=min(c,ans);37         }38     }39     40     if(ans==0) cout<<-1;41     else  cout<