Arthur and Table CodeForces

首先，按长度排序。

长度为p的桌腿有a[p]个。

要使得长度为p的桌腿为最长，那么要按照代价从小到大砍掉sum{长度不到p的腿的数量}-a[p]+1条腿。还需要将所有长于p的桌腿砍光。枚举p即可。

要点（看了题解才明白）：可以通过精力最高只有200的条件，大大缩小时间/空间复杂度。

恩，所以...这是贪心吧？

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 struct Leg

 {

     int len,cost,len2;

     bool operator<(const Leg& b) const

     {

         return len<b.len||(len==b.len&&cost<b.cost);

     }

 }l[];

 int l2[];

 int sum1,n,ans=0x3f3f3f3f,now,now2,now3,sum2;

 int main()

 {

     int i,j;

     scanf("%d",&n);

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

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

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

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

     sort(l+,l+n+);

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

         if(l[i].len!=l[i-].len)

             l[i].len2=l[i-].len2+;

         else

             l[i].len2=l[i-].len2;

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

         sum2+=l[i].cost;

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

     {

         sum2-=l[i].cost;

         now++;

         if(l[i].len2==l[i+].len2)    continue;

         now2=sum1-now+;

         if(now2<=)

         {

             ans=min(sum2,ans);

         }

         else

         {

             now3=;

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

             {

                 if(l2[j]>=now2)

                 {

                     now3+=j*now2;

                     break;

                 }

                 now2-=l2[j];

                 now3+=j*l2[j];

             }

             ans=min(now3+sum2,ans);

         }

         for(j=i;l[j].len2==l[j-].len2;j--)

             l2[l[j].cost]++;

         l2[l[j].cost]++;

         sum1+=now;

         now=;

     }

     printf("%d",ans);

     return ;

 }

巴特西

Arthur and Table CodeForces - 557C

最新文章

热门文章