3 条题解
-
1
/*两种方法,核心思想都是跳过最长的几个无牛区 第二种方法较快:直接用输入的数据计算无牛区的长度 第一种方法:用数组模拟牛棚,0无1有*/ #include<bits/stdc++.h> using namespace std; int a[300],b,c,d,e,f[300]; //num line,board num,total num,ox num,temp,blank length bool way(int a,int b) { return a>b; } int main() { int b,c,d,e; cin>>b>>c>>d; //way 2: for (int i=0;i<d;i++) cin>>a[i]; sort (a,a+d); for (int i=0;i<d-1;i++) f[i]=a[i+1]-a[i]-1;//count the blank e=a[d-1]-a[0]+1;//from the first to the last sort (f,f+c,way);//sort the blank length for (int i=0;i<b-1;i++) e-=f[i];//cut form the middle,take out the rest //--------changable part end--------- cout<<e; return 0; } //way 1: //for (int i=0;i<d;i++) // { // cin>>e; // a[e]=1; // }//mark ox position // e=0; // for (int i=1;i<=c;i++) // if (a[i]==1)//begin from the first ox // { // for (int j=i;j<=c;j++) // { // if (a[j]==0) // e++;//connected cowshed count // if (a[j]==1) // { // f[j]=e; // e=0;//take num to f[],recount // } // } // i=c; // } // e=c; // sort (f,f+c+1,way);//sort the blank length // for (int i=0;i<b-1;i++) // e-=f[i];//cut form the middle,take out the rest // for (int i=1;i<=c;i++) // { // if (a[i]==0) // e--; // else // break; // }//except front blank // for (int i=c;i>=0;i--) // { // if (a[i]==0) // e--; // else // break; // }//except back blank
-
1
/*典型的贪心问题,这个问题实质上就是问你,一块长度为a[c]-a[1](最后一头牛与第一头牛之间的距离) 砍m-1次,求最小长度,那我们只要找到两头牛之间距离的大的数值减掉即可~*/ #include<bits/stdc++.h> using namespace std; int a[1001],f[1001];//a是牛所在牛棚序号,f是牛棚差值 int m,s,c,ans; bool cmp(int x,int y)//sort用的比较函数(从大到小排) { return x>y; } int main() { cin>>m>>s>>c; for(int i=1;i<=c;i++) scanf("%d",&a[i]); if(m>c)//特判,如果木板数大于牛总数,那么每一头牛都可以获得一块木板,最小就是c { printf("%d\n",c); return 0; } sort(a+1,a+c+1); ans=a[c]-a[1]+1; for(int i=2;i<=c;i++) { f[i-1]=a[i]-a[i-1];//求每相邻两头牛差的值 } sort(f+1,f+c,cmp);//从大到小排 for(int i=1;i<=m-1;i++)//砍m-1次 { ans=ans-f[i]+1; } cout<<ans; return 0; }
- 1
信息
- ID
- 13
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 36
- 已通过
- 14
- 上传者