首页 > > 程序设计 > C/C++ >

Arthur and Table CodeForces - 557C

2018-06-17 21:53:39来源：未知阅读 ()

首先，按长度排序。

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

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

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

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

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 struct Leg
 5 {
 6     int len,cost,len2;
 7     bool operator<(const Leg& b) const
 8     {
 9         return len<b.len||(len==b.len&&cost<b.cost);
10     }
11 }l[100100];
12 int l2[210];
13 int sum1,n,ans=0x3f3f3f3f,now,now2,now3,sum2;
14 int main()
15 {
16     int i,j;
17     scanf("%d",&n);
18     for(i=1;i<=n;i++)
19         scanf("%d",&l[i].len);
20     for(i=1;i<=n;i++)
21         scanf("%d",&l[i].cost);
22     sort(l+1,l+n+1);
23     for(i=1;i<=n;i++)
24         if(l[i].len!=l[i-1].len)
25             l[i].len2=l[i-1].len2+1;
26         else
27             l[i].len2=l[i-1].len2;
28     for(i=1;i<=n;i++)
29         sum2+=l[i].cost;
30     for(i=1;i<=n;i++)
31     {
32         sum2-=l[i].cost;
33         now++;
34         if(l[i].len2==l[i+1].len2)    continue;
35         now2=sum1-now+1;
36         if(now2<=0)
37         {
38             ans=min(sum2,ans);
39         }
40         else
41         {
42             now3=0;
43             for(j=0;j<=200;j++)
44             {
45                 if(l2[j]>=now2)
46                 {
47                     now3+=j*now2;
48                     break;
49                 }
50                 now2-=l2[j];
51                 now3+=j*l2[j];
52             }
53             ans=min(now3+sum2,ans);
54         }
55         for(j=i;l[j].len2==l[j-1].len2;j--)
56             l2[l[j].cost]++;
57         l2[l[j].cost]++;
58         sum1+=now;
59         now=0;
60     }
61     printf("%d",ans);
62     return 0;
63 }