20230319

admin

[C++] 纯文本查看 复制代码

struct tea
{
	int w;
	int v;
}t[100];

bool cmp(tea a,tea b)
{
	return a.v<b.v;
}

void kache1()//卡车装货 结构体方式 
{
	int m,n,s=0,cnt;

	memset(t,0,sizeof(t));
	
	cin>>m>>n;
	for(int i=0;i<n;i++)
	{
		cin>>t[i].w>>t[i].v;
	}
	
	sort(t,t+n,cmp);
	
	cnt=n-1;
	while(1)
	{
		if(m>=t[cnt].w)
		{
			s+=t[cnt].v*t[cnt].w;
			m-=t[cnt].w;
			cnt--;
		}
		else if(m>0)
		{
			s+=t[cnt].v*m;
			m=0;	
		}
		else break;
		if(cnt<0) break;
	} 
	
	cout<<s;
}

void qujian1()//不相交区间 
{
	int n,cnt=0;
	memset(t,0,sizeof(t));//借用上题的结构体 
	
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>t[i].w>>t[i].v;//头 尾 
	}
	
	sort(t,t+n,cmp);//以尾排序
	
	int temp=t[0].v;//记录首段末尾 
	for(int i=1;i<n;i++)
	{
		if(t[i].w>temp)
		{
			temp= t[i].v;
			cnt++;
		}	
	}
	cout<<cnt+1;
}

bool cmp1(tea a,tea b)
{
	return a.w<b.w;
}
void qujian2()//区间选点
{
	int n,cnt=0;
	memset(t,0,sizeof(t));//借用上题的结构体 
	
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>t[i].w>>t[i].v;//头 尾 
	}
	
	sort(t,t+n,cmp1);//以头排序
	int temp=t[0].v;//记录首段末尾
	
	for(int i=1;i<n;i++)
	{
		if(t[i].w>=temp) continue;
		else
		{
			cnt++;
			temp=t[i].v;
		}
	}
	cout<<cnt+1;
} 

void qujian3()//区间覆盖
{
	int n,cnt=0,i=0;
	int w1,v1;
	cin>>w1>>v1;
	memset(t,0,sizeof(t));//借用上题的结构体 
	
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>t[i].w>>t[i].v;//头 尾 
	}
	
	sort(t,t+n,cmp);//以尾排序
	int temp=t[0].v;//记录首段末尾
	int flag=0;//未找到符合的区间 
	//int flag1=0;//能够找到下一个扩展区间. 
	int t1=w1;
	while(1)//for(int i=0;i<n;i++)
	{
		flag=0;
		if(t[i].w<t1)&&(t[i].v>t1)
		{
			flag=1;
			if(t[i].v>v1)
			{
				flag=2;
				break;
			} 
			temp=i;//找到能够覆盖左边界的最长的区间 
		}
		if(i==n-1)
		{
			if(flag==0)	break;
			t1=t[temp].v//以此点为左边界，继续循环找能覆盖的 最长的区间 
			i=temp+1;//从下行开始找 
			if(i==n)	break;//搜到底了也没有 
			cnt++;
		}
		else
		{
			i++;
		}	
	} 
	
}