CodeForces 557C Arthur and Table STL的使用

题意：一个桌子有n条腿，每条腿有一定的长度l，和砍下的花费w，现在规定，桌子稳的条件是长度最长的腿（可多个）的数量大于长度小于它的桌子腿数量，且不存在比他还长的桌子腿，求让桌子腿稳定的最小的花费

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <queue>

#include <map>

#include <algorithm>

#include <set>

using namespace std;

typedef long long ll;

const double eps = 1e-;

const int inf = 0x3f3f3f3f;

const double pi=acos(-);

const int mod=;

int max(int a,int b)

{return a>b?a:b;};

int min(int a,int b)

{return a<b?a:b;};

const int maxl=;

struct node{

   int l,w;

}ne[];

bool cmp(node a,node b)

{

    return a.l<b.l;

}

vector<int> numw[];

int n,num[maxl+],total[maxl+];

void solve()

{

    int ans=inf;

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

      if(num[i])

      {

        int temp=total[i+],k=num[i]-num[i+];

        int cnt=num[]-num[i]-(k-);

        if(cnt>)

        {

         for(int j=;j<=;j++)

            if(numw[j].size())

            {

                //printf(":2\n");

                if(cnt<=) break;

                int p=lower_bound(numw[j].begin(),numw[j].end(),i)-numw[j].begin();//花费为j的桌子腿中长度>=i的个数

                temp+=min(p,cnt)*j;

                cnt-=p;

               // printf(":3\n");

            }

        }

        ans=min(ans,temp);

        }

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

}

void init()

{

    memset(total,,sizeof(total));

    memset(num,,sizeof(num));

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

        numw[i].clear();

}

void input()

{

    init();

   //printf("||5\n");

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

       {

         scanf("%d",&ne[i].l);

         num[ne[i].l]++;

       }

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

       {

           scanf("%d",&ne[i].w);

           numw[ne[i].w].push_back(ne[i].l);

       }

    //printf("|||6\n");

    sort(ne+,ne+n+,cmp);

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

    {

        int p=i;

        while(ne[p].l==ne[i].l&&i<=n)

            {

                total[ne[p].l]+=ne[i].w;

                i++;

            }

    }

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

         {

             total[i]+=total[i+];

             num[i]+=num[i+];

         }//total数组统计砍下长度>=i的所有桌子腿的总花费
         //num数组记录长度>=i的桌子腿的个数

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

         if(numw[i].size())

             sort(numw[i].begin(),numw[i].end());

}

int main()

{

    while(~scanf("%d",&n))

    {

       input();

       solve();

    }

    return ;

}

核心思路：先暴力枚举最长的桌子腿腿长（1e5），然后再按花费（<=200）进行从小到大的贪心选取

，每次在花费为w上进行贪心时，找出小于当前枚举的长度的桌子腿个数，本题的实现是个大难题

错因分析：本来想用优先队列来维护权花费为w的长度序列的，实现本代码中vector的操作，但是优先队列

没有迭代器，不支持begin()这个操作，也就是priority_queue<node> a[100]，a[1]就是代表一个优先队列，没有a[1].begin()这个操作，事实上优先队列只有pop(),top(),和insert()，这三个操作，其实就是个堆。