首页 > 代码库 > Barn Repair
Barn Repair
链接
分析:我们不断统计相邻两个元素之间的差值,按照差值从大到小排序,在进行贪心即可
1 /* 2 PROB:barn1 3 ID:wanghan 4 LANG:C++ 5 */ 6 #include "iostream" 7 #include "cstdio" 8 #include "cstring" 9 #include "string" 10 #include "cmath" 11 #include "algorithm" 12 using namespace std; 13 const int maxn=220; 14 int m,s,c; 15 int stall[maxn]; 16 struct Node 17 { 18 int sub,id; 19 }; 20 Node p[maxn]; 21 bool cmp(Node x,Node y){ 22 return x.sub>y.sub; 23 } 24 int vis[maxn]; 25 int main() 26 { 27 freopen("barn1.in", "r", stdin); 28 freopen("barn1.out", "w", stdout); 29 cin>>m>>s>>c; 30 for(int i=0;i<c;i++){ 31 cin>>stall[i]; 32 } 33 sort(stall,stall+c); 34 for(int i=1;i<c;i++){ 35 p[i].id=i; 36 p[i].sub=stall[i]-stall[i-1]; 37 } 38 //p[c].id=c; 39 //p[c].sub=s-stall[c-1]; 40 sort(p+1,p+c,cmp); 41 if(m>=c){ 42 cout<<c<<endl; 43 }else{ 44 int cnt=stall[c-1]-stall[0]; 45 //cout<<cnt<<endl; 46 for(int i=1;i<m;i++){ 47 cnt-=p[i].sub; 48 //cout<<"sub:"<<p[i].sub<<endl; 49 //cout<<cnt<<endl; 50 } 51 cout<<cnt+m<<endl; 52 } 53 }
Barn Repair
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。