首页 > 代码库 > Bucharest, Romania 2013 A Russian Dolls 贪心

Bucharest, Romania 2013 A Russian Dolls 贪心

2024-07-18 00:10:14   224人阅读

题意：俄罗斯有一种玩具叫做套娃，一个大的只能嵌套一个比它内体积小的套娃 ，给你每个套娃的内体积和外体积，每个套娃内体积单位空体积的消耗，问你怎么样安排才能使得花费最小。

解题思路：这里我们知道，是优先去花费最大的那个套娃并且填掉它。

解题代码：

 1 // File Name: 12895.cpp 2 // Author: darkdream 3 // Created Time: 2014年08月16日 星期六 23时41分13秒 4  5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long25 26 using namespace std;27 struct node{28     int x, y , c,ok;29 }a[1005];30 int cmp(node a, node b)31 {32     return a.c > b.c ; 33 }34 int main(){35     int n ; 36     while(scanf("%d",&n)!= EOF)37     {38         memset(a,0,sizeof(a));39         for(int i = 1;i <= n;i ++)40         {41             scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c) ;42             a[i].ok = 1;43         }44         sort(a+1,a+1+n,cmp);45         LL ans = 0 ; 46         for(int i = 1;i <= n;i ++)47         {48             int site = 0 ; 49             int mx = 0;50             for(int j = 1;j <= n;j ++)51             {52                 if(a[j].ok && a[i].y  >  a[j].x )53                 {54                     if(a[j].x > mx)55                     {56                         mx = a[j].x;57                         site = j ; 58                     }59                 }60             }61             if(site)62             {63                 a[site].ok = 0 ;64             }65             ans += (a[i].y - mx)*a[i].c ; 66         }67         printf("%I64d\n",ans);68     }        69     return 0;70 }
View Code

 


联系
我们