首页 > 代码库 > Bucharest, Romania 2013 A Russian Dolls 贪心
Bucharest, Romania 2013 A Russian Dolls 贪心
题意:俄罗斯有一种玩具叫做套娃,一个大的只能嵌套一个比它内体积小的套娃 ,给你每个套娃的内体积和外体积,每个套娃内体积单位空体积的消耗,问你怎么样安排才能使得花费最小。
解题思路:这里我们知道,是优先去花费最大的那个套娃并且填掉它。
解题代码:
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。