有做面食的网站吗,网站代理网址,mm 263企业邮箱登录,伍佰亿搜索引擎网站系统虽然只是10^6的数据量#xff0c;但用cin会tle。一直知道cin常数大#xff0c;但没想到会是10^2这个级别。 我们枚举每个power的lamp#xff0c;然后对每个power用平均logn的代价去求它的cost#xff0c;最后取最小值 对于每个power#xff0c;我们从左往右地去照亮整个区…虽然只是10^6的数据量但用cin会tle。一直知道cin常数大但没想到会是10^2这个级别。 我们枚举每个power的lamp然后对每个power用平均logn的代价去求它的cost最后取最小值 对于每个power我们从左往右地去照亮整个区间首先0点要插一个路灯下一个路灯理想上想插在0power的位置这样区间不被重复照亮但实际上power位置上的路灯可能被blocked了所以我们想在power位置之前的离power最近的一个位置安装路灯。如果发现最近的那个位置离power的位置大于power了那power位置永远不会被照亮返回-1 这样贪心实际上每次算cost的代价是 n/power为什么平均意义下是logn的呢。 因为整体下来是n/1n/2n/3n/4...n/k可见k越大整体复杂度越高我们考虑其上限及kn的情况得到n(11/21/31/4...1/n)而11/21/31/41/5...1/n这个数列求和是logn级别的因为可以把1/31/4看成1/21/51/61/71/8看成1/2接下来的每8项16项都是1/2。然后把n看成2^k的话也可以把n看成2^02^12^2...2^k-1其中每一份都对数列的和贡献出1/2所以这个数列求和是1/2*logn左右及logn级别的。 1 #includeiostream2 using namespace std;3 4 int n,m,k;//长度为nm个5 int cost[1000005],blocked[1000005],last_unblocked[1000005];6 long long ans;7 int main()8 { 9 cinnmk;
10 for(int i1;im;i){
11 int x; scanf(%d,x);
12 blocked[x]1;
13 }
14 for(int i1;ik;i) scanf(%d,cost[i]); //power为i的lamp花费cost[i]
15 if(blocked[0]) { cout-1; return 0; }
16
17 int last0;
18 for(int i1;in;i){
19 if(!blocked[i]) lasti;
20 last_unblocked[i]last;
21 }
22 for(int i1;ik;i){//模拟用每个power的路灯
23 long long c0;
24 for(int index0;indexn; ){//index是每一个要插路灯的位置
25 ccost[i];
26 if(indexin) indexn;
27 else{
28 int loclast_unblocked[indexi];//下一个路灯想插在indexi但这里可能被blocked了那想照亮这个地方就找这个位置前面最近能放路灯的位置
29 if(locindex) { c-1; break; }
30 indexloc;
31 }
32 }
33 if(c-1) continue;
34 else{
35 if(ans0) ansc;
36 else ansmin(c,ans);
37 }
38 }
39
40 if(ans0) cout-1;
41 else coutans;
42 return 0;
43 } 转载于:https://www.cnblogs.com/ZhenghangHu/p/9191168.html
