虽然只是 10^6 的数据量, 但用 cin 会 tle. 一直知道 cin 常数大, 但没想到会是 10^3 这个级别, 而且比 scanf 慢 5 倍左右.
我们枚举每个 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 级别的.
- #include<iostream>
- using namespace std;
- int n,m,k;// 长度为 n,m 个
- int cost[1000005],blocked[1000005],last_unblocked[1000005];
- long long ans;
- int main()
- {
- cin>>n>>m>>k;
- for(int i=1;i<=m;i++){
- int x; scanf("%d",&x);
- blocked[x]=1;
- }
- for(int i=1;i<=k;i++) scanf("%d",&cost[i]); //power 为 i 的 lamp 花费 cost[i]
- if(blocked[0]) { cout<<-1; return 0; }
- int last=0;
- for(int i=1;i<=n;i++){
- if(!blocked[i]) last=i;
- last_unblocked[i]=last;
- }
- for(int i=1;i<=k;i++){// 模拟用每个 power 的路灯
- long long c=0;
- for(int index=0;index<n; ){//index 是每一个要插路灯的位置
- c+=cost[i];
- if(index+i>=n) index=n;
- else{
- int loc=last_unblocked[index+i];// 下一个路灯想插在 index+i, 但这里可能被 blocked 了, 那想照亮这个地方就找这个位置前面最近能放路灯的位置
- if(loc<=index) { c=-1; break; }
- index=loc;
- }
- }
- if(c==-1) continue;
- else{
- if(ans==0) ans=c;
- else ans=min(c,ans);
- }
- }
- if(ans==0) cout<<-1;
- else cout<<ans;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2647104.html