【贪心堆】luoguP2672 推销员

堆维护，贪心做法

题目描述

阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有N家住户，第i家住户到入口的距离为Si米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的X家住户推销产品，然后再原路走出去。

阿明每走1米就会积累1点疲劳值，向第i家住户推销产品会积累Ai点疲劳值。阿明是工作狂，他想知道，对于不同的X，在不走多余的路的前提下，他最多可以积累多少点疲劳值。

输入输出格式

输入格式：

第一行有一个正整数N，表示螺丝街住户的数量。

接下来的一行有N个正整数，其中第i个整数Si表示第i家住户到入口的距离。数据保证S1≤S2≤…≤Sn<10^8。

接下来的一行有N个正整数，其中第i个整数Ai表示向第i户住户推销产品会积累的疲劳值。数据保证Ai<10^3。

输出格式：

输出N行，每行一个正整数，第i行整数表示当X=i时，阿明最多积累的疲劳值。

这题在2016年做过，不过全WA了hhh……

好吧今天提交4次前两次也是全WA……

最初的思路

假设现在右端点为i-1,有i优于j(i < j)那么有wi+2(s[i]-s[i-1])>wj+2(s[j]-s[i-1])即wi+2si>wj+2sj

定义距离s[]，疲劳值w[]，f[i]表示在i..n中(2si+wi)最大值的编号。那么我们每次处理1..now-1的w[]最大值和value(f[i+1])两者最大值。重复这一过程。

然而这个做法在调试时候就叉掉了……

第一次WA

非常NAIVE地把左右两边用了一个堆维护value()最小值，pretest过了就交了……

但是这个value()与max_right_border有关系，所以这个堆是个假堆……

 #include<bits/stdc++.h>

 using namespace std;

 const int N = 1e5;

 int n,s[N],w[N],f[N],now,sum,rx;

 bool vis[N];

 int reval(int a)

 {

     if (a >= rx)return w[a]+*(s[a]-s[rx]);

     return w[a];

 }

 struct cmp

 {

     bool operator () (int &a, int &b) const

     {

         return reval(a) < reval(b);

     }

 };

 priority_queue<int, vector<int>, cmp> p,q;

 int deal(int x)

 {

     if (x <= )return ;

     while ((!q.empty())&&vis[q.top()])q.pop();

     if (q.empty())return ;

     return q.top();

 }

 int dear(int x)

 {

     while ((!p.empty())&&(vis[p.top()]))p.pop();

     if (p.empty())return ;

     return p.top();

 }

 int main()

 {

     scanf("%d",&n);

     for (int i=; i<=n; i++)scanf("%d",&s[i]);

     for (int i=; i<=n; i++){scanf("%d",&w[i]);p.push(i);}

     f[n] = n;

     for (int i=n-; i>=; i--)

         if (*s[i]+w[i] > *s[f[i+]]+w[f[i+]])

             f[i] = i;

         else f[i] = f[i+];

     now = ;rx = ;

     for (int i=; i<=n; i++)

     {

         int dl = deal(now-);

         int dr = dear(now+);

         if (reval(dl) > reval(dr)){

             now = dl;

             vis[dl] = ;

             sum += reval(dl);

         }else{

             sum += reval(dr);

             if (rx < dr){

                 for (int j=now+; j<=dr; j++) q.push(j);

                 rx = dr;

             }

             now = dr;

             vis[dr] = ;

         }

         printf("%d\n",sum);

     }

     return ;

 }

第二次WA

观察变量调试重写了三十分钟，（此时并没有意识到假堆的严重性），看着调试输出还以为堆不假了（flag）。

在查询时候，又多放了一个堆来解决：查询左边时候q.top()却在now右边的情况（反之亦然）。这pretest设计得真好

按道理这样应该比第一次WA要慢一些，结果却快了200ms+...

反正都是全WA

 #include<bits/stdc++.h>

 using namespace std;

 const int N = 1e5;

 int n,s[N],w[N],f[N],now,sum,rx;

 bool vis[N];

 int reval(int a)

 {

     if (a >= rx)return w[a]+*(s[a]-s[rx]);

     return w[a];

 }

 struct cmp

 {

     bool operator () (int &a, int &b) const

     {

         return reval(a) < reval(b);

     }

 };

 priority_queue<int, vector<int>, cmp> p,q;

 int deal(int x)

 {

     if (x <= )return ;

     queue<int>tt;

     while ((!q.empty())&&(q.top()>now||vis[q.top()]))

     {

         while ((!q.empty())&&(vis[q.top()]))q.pop();

         while ((!q.empty())&&(q.top()>now)){tt.push(q.top());q.pop();}

     }

     if (q.empty())return ;

     int xx = q.top();

     while (!tt.empty()){q.push(tt.front());tt.pop();}

     return xx;

 }

 int dear(int x)

 {

     queue<int>tt;

     if (rx == n)return ;

     if(rx!=n)while ((!p.empty())&&(p.top()<now||vis[p.top()]))

     {

         while ((!p.empty())&&(vis[p.top()]))p.pop();

 //        printf("ptop:%d\n",p.top());

         while((!p.empty())&&(p.top()<now)){tt.push(p.top());p.pop();}

     }

     if (p.empty())return ;

     int xx = p.top();

     while (!tt.empty()){p.push(tt.front());tt.pop();}

     return xx;

 }

 int main()

 {

     scanf("%d",&n);

     for (int i=; i<=n; i++)scanf("%d",&s[i]);

     for (int i=; i<=n; i++){scanf("%d",&w[i]);p.push(i);}

     f[n] = n;

     for (int i=n-; i>=; i--)

         if (*s[i]+w[i] > *s[f[i+]]+w[f[i+]])

             f[i] = i;

         else f[i] = f[i+];

     now = ;rx = ;

 //    for (int i=1; i<=n; i++)printf("%d ",f[i]);printf("#\n");

     for (int i=; i<=n; i++)

     {

         int dl = deal(now-);

         int dr = dear(now+);

 //        printf("now:%d rx:%d dl:%d %d-dr:%d %d\n",now,rx,dl,reval(dl),dr,reval(dr));

         if (reval(dl) >= reval(dr)){

             now = dl;

             vis[dl] = ;

             sum += reval(dl);

         }else{

             sum += reval(dr);

             if (rx < dr){

                 for (int j=rx+; j<=dr; j++) q.push(j);

                 rx = dr;

             }

             now = dr;

             vis[dr] = ;

         }

 //        for (int i=1; i<=n; i++)printf("%d ",vis[i]);puts("@");

         printf("%d\n",sum);

     }

         int dl = deal(now-);

         int dr = dear(now+);

 //        printf("now:%d rx:%d dl:%d %d-dr:%d %d\n",now,rx,dl,reval(dl),dr,reval(dr));

     return ;

 }

第一次TLE

好气啊打了一发纯粹的暴力（天哪有60分）

 #include<bits/stdc++.h>

 using namespace std;

 const int N = 1e5+;

 int n,s[N],w[N],rx,now,sum;

 int a,b;

 bool vis[N];

 int reval(int x)

 {

     if (x < rx)return w[x];

     return w[x] + *(s[x]-s[rx]);

 }

 int main()

 {

     scanf("%d",&n);

     for (int i=; i<=n; i++)scanf("%d",&s[i]);

     for (int i=; i<=n; i++)scanf("%d",&w[i]);

     for (int k=; k<=n; k++)

     {

         a = , b = ;

         int cmp = , lb;

         for (int i=; i<now; i++)

             if ((!vis[i])&&(a < w[i]))a = w[b = i];

         cmp = a;lb = b;

         a = ,b = ;

         for (int i=now+; i<=n; i++)

             if ((!vis[i])&&(a < reval(i)))

                 a = reval(i),b = i;

         if (a > cmp){cmp = a;lb = b;}

         rx = max(rx, lb);

         vis[lb] = ;

         now = lb;

         sum += cmp;

         printf("%d\n",sum);

     }

     return ;

 }

正解AC

在打完暴力之后豁然开朗（？？？）意识到右部分大于max_right_border的枚举即可，这样一来左边的就变为小于max_right_border的部分，由此无所谓在now左部分的元素变动情况，从而可以保证堆的正确性。

 #include<bits/stdc++.h>

 using namespace std;

 const int N = 1e5+;

 int n,s[N],w[N],rx,now,sum;

 int a,b;

 bool vis[N];

 struct cmp

 {

     bool operator() (int &a, int &b)

     {

         return w[a] < w[b];

     }

 };

 priority_queue<int, vector<int>, cmp>q;

 void find()

 {

     while ((!q.empty())&&(vis[q.top()]))q.pop();

     if (q.empty())return;

     b = q.top();a = w[b];

 }

 int main()

 {

     scanf("%d",&n);

     for (int i=; i<=n; i++)scanf("%d",&s[i]);

     for (int i=; i<=n; i++)scanf("%d",&w[i]);

     for (int k=; k<=n; k++)

     {

         a = , b = ;

         int cmp = , lb;

         find();

         cmp = a;lb = b;

         a = ,b = ;

         for (int i=rx+; i<=n; i++)

             if ((!vis[i])&&(a < w[i] + *(s[i]-s[rx])))

                 a = w[i] + *(s[i]-s[rx]),b = i;

         if (a > cmp)

         {

             cmp = a;

             lb = b;

         }

         if (rx < lb)

         {

             for (int i=rx+; i<=lb; i++)q.push(i);

             rx = lb;

         }

         vis[lb] = ;

         now = lb;

         sum += cmp;

         printf("%d\n",sum);

     }

     return ;

 }

巴特西

【贪心堆】luoguP2672 推销员

题目描述

输入输出格式

最初的思路

第一次WA

第二次WA

第一次TLE

正解AC

最新文章

热门文章

巴特西

【贪心 堆】luoguP2672 推销员

题目描述

输入输出格式

最初的思路

第一次WA

第二次WA

第一次TLE

正解AC

最新文章

热门文章

【贪心堆】luoguP2672 推销员