3 条题解

  • 1
    @ 2022-12-25 15:54:13
    /*两种方法,核心思想都是跳过最长的几个无牛区
    第二种方法较快:直接用输入的数据计算无牛区的长度
    第一种方法:用数组模拟牛棚,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
      @ 2022-12-14 23:39:57
      /*典型的贪心问题,这个问题实质上就是问你,一块长度为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;
      } 
      
      • 0
        @ 2022-12-25 15:22:02

        注意:牛的位置并未按从小到大给出

        • 1

        信息

        ID
        13
        时间
        1000ms
        内存
        256MiB
        难度
        5
        标签
        递交数
        36
        已通过
        14
        上传者