NOIP2015 T4 推销员贪心+堆优化

前几天在学堆，这个数据结构貌似挺简单的，但是我看了很久啊QAQ...

今天算是搞懂了吧...于是想到了这道题...（当初悄悄咪咪看题解记得一点）

点我看题

放洛谷的题...

题意的话，大概就是有n个房子在一条直线上，每个房子有一个离起点的距离，还有一个价值。

然后n个询问，第 i 个表示选 i 个房子能得到的最大总价值。总价值指最远距离*2+每一个推销房子的价值。

有一个前提，不多走路，也就是说这个最远距离必须是某个要推销的房子。

思路：我萌可以考虑一下贪心，对于第i个询问，是否可以从第 i-1 个询问的基础上来得到捏？

当然可以辣！（然而不会证明QAQ）

辣我萌就假装证明完了的样子，

所以第 i 个询问的答案只需要在第 i-1 的询问答案加上一个最优值，也就是选择一个地方进行推销。

我萌可以这样考虑，假设在第 i-1 个询问的答案为lastans，这个最优解当前的最远房子为max

然后分类讨论，对于一个房子 x ，如果在max左边（x<max），辣么这个房子对答案的影响为 a[x]。

　　　　　　　　　　　　　　如果在max右边（x>max），辣么这个房子对答案的影响为 s[x]*2+a[x]-s[max]*2。

所以我萌每次都在去枚举一重 x 找到影响最大的，然后输出 lastans+影响值。

并更新 lastans和max。

但对于100%的数据O(n^2)是要tle的，辣就想想优化。

找最大值！会想到很多数据结构都可以维护。这里我选了刚学的堆。当然有很大原因是因为之前看的题解是堆

如何去优化捏。这样考虑，对于 x<max 的情况建一个堆heap0，对于 x>max 的情况建一个堆heap1。

刚开始的时候把heap1这个堆初始为全部 s[i]*2+a[i] (1≤i≤n) heap0这个堆初始为空。

然后每次查询前，如果heap1的堆首是<=max的就都删掉。

比较一下heap1的堆首和heap0的堆首，更新。

如果heap1的堆首更优，就把所有没在heap0堆的且小于新max的都加入到heap0堆里。

这题我觉得题灰常的好啊QAQ，毕竟花了好久才搞出来...不过必须吐槽官方数据太弱了...

  1 type
  2   node=record
  3       num:longint;
  4       id:longint;
  5   end;
  6 var n,i,j:longint;
  7     num,lastans:longint;
  8     max,x:longint;
  9     s,a:array[0..100000]of longint;
 10     v:array[0..100000]of boolean;
 11     heap:array[0..100000,0..1]of node;
 12 
 13     tot,tot0:longint;
 14 procedure swap(var a,b:node);
 15 var t:node;
 16 begin
 17   t:=a;a:=b;b:=t;
 18 end;
 19 procedure down(x,b:longint);
 20 begin
 21   while x*2<=n do
 22   begin
 23     if heap[x*2,b].num>heap[x*2+1,b].num then
 24     begin
 25       if heap[x,b].num<heap[x*2,b].num then
 26       begin
 27         swap(heap[x,b],heap[x*2,b]);
 28         x:=x*2;
 29       end else break;
 30     end else
 31     begin
 32       if heap[x,b].num<heap[x*2+1,b].num then
 33       begin
 34         swap(heap[x,b],heap[x*2+1,b]);
 35         x:=x*2+1;
 36       end else break;
 37     end;
 38   end;
 39 end;
 40 procedure up(x:longint);
 41 begin
 42   while x>1 do
 43   begin
 44     if heap[x div 2,0].num<heap[x,0].num then
 45     begin
 46       swap(heap[x div 2,0],heap[x,0]);
 47       x:=x div 2;
 48     end else break;
 49   end;
 50 end;
 51 procedure build(n:longint);
 52 var i:longint;
 53 begin
 54   for i:=n div 2 downto 1 do
 55   down(i,1);
 56 end;
 57 begin
 58   read(n);
 59   for i:=1 to n do
 60   read(s[i]);
 61   for i:=1 to n do
 62   read(a[i]);
 63   for i:=1 to n do
 64   begin
 65     heap[i,1].num:=s[i]*2+a[i];
 66     heap[i,1].id:=i;
 67   end;
 68   tot:=n;
 69   build(n);
 70   for i:=1 to n do
 71   begin
 72     while (heap[1,1].id<=max)and(tot>0) do
 73     begin
 74       heap[1,1].num:=0;
 75       swap(heap[1,1],heap[tot,1]);
 76       down(1,1);
 77       dec(tot);
 78     end;
 79     if (heap[1,0].num+lastans>num) then
 80     begin
 81       num:=lastans+heap[1,0].num;
 82       x:=heap[1,0].id;
 83     end;
 84     if heap[1,1].num+lastans-s[max]*2>num then
 85     begin
 86       num:=heap[1,1].num+lastans-s[max]*2;
 87       x:=heap[1,1].id;
 88       for j:=1 to x-1 do
 89       if not v[j] then
 90       begin
 91         v[j]:=true;
 92         inc(tot0);
 93         heap[tot0,0].num:=a[j];
 94         heap[tot0,0].id:=j;
 95         up(tot0);
 96       end;
 97       max:=x;
 98     end;
 99     writeln(num);
100     lastans:=num;
101     if x<max then
102     begin
103       heap[1,0].num:=0;
104       swap(heap[1,0],heap[tot0,0]);
105       down(1,0);
106       dec(tot0);
107     end;
108   end;
109 end.
110 
111 //堆的维护都是自己写的，很丑啊QAQ

NOIP2015 T4

NOIP2015 T4 推销员 贪心+堆优化

NOIP2015 T4 推销员贪心+堆优化