AtCoder 195 B，C，D

最新推荐文章于 2025-03-12 13:19:40 发布

睡神...

最新推荐文章于 2025-03-12 13:19:40 发布

阅读量408

点赞数

分类专栏：贪心综合题（比赛）文章标签：贪心算法暴力

本文链接：https://blog.csdn.net/IT_shao/article/details/115091806

版权

综合题（比赛）同时被 2 个专栏收录

21 篇文章

订阅专栏

贪心

4 篇文章

订阅专栏

本文概述了AtCoder比赛ABC195中的三个问题：B-ManyOranges的范围调整策略，C-Comma的简单字符划分算法，以及D-ShippingCenter的背包与盒子组合优化。通过实例展示了贪心算法在D题中的应用，以及如何在不同场景下选择合适的策略。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

AtCoder 195

https://atcoder.jp/contests/abc195/tasks

B - Many Oranges

可以枚举放的个数n，w的值只要在a*n和b*n之间就一定有办法去调整，就一定可以

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int a,b,w;
	cin>>a>>b>>w;
	w*=1000;
	
	int minv=1e9,maxv=0;
	for(int i=1;i<=1000000;i++)
	{
		if(w>=a*i&&w<=b*i)
		{
			maxv=max(maxv,i);
			minv=min(minv,i);
		}
	}
	if(maxv==0||minv==0) cout<<"UNSATISFIABLE";
	else cout<<minv<<' '<<maxv;
	return 0;
 }

C - Comma

c题题面很简单，就是三位一断，加逗号。问1到n这些数中，一共要加多少个逗号？~~翻跟没翻差别不大~~

n是<=10^5，所以可以直接暴力。

D - Shipping Center

我们有n个背包，m个盒子。每个背包都会有个容量和价值，每一个box也会有一个容量。然后会有q个查询，每个查询中，都会给个l,r，意思是 $[l,r]$ 这个区间的box都不可用，问用剩余盒子装出的最大价值为多少？

分析：

这题没什么特别的，数据也不是很大，很容易让人联想到贪心。主要有以下两种贪心策略：

1.将背包价值从大到小排列，将box的容量从小到大排列，目的是让尽量小的box装下尽量的val

2.将背包和box的容量从小到大排列，尽量多的去装。

我用的是第一种，但要注意记录下标，排完序以后，区间会乱，这时候如果开数组打勾是不对的。

Code：

C

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,ans;
int main()
{
   cin>>n;
   if(n>=1000) 	ans+=n-999;
   if(n>=1000000) 	ans+=n-999999;
   if(n>=1000000000) 	ans+=n-999999999;
   if(n>=1000000000000) 	ans+=n-999999999999;
   if(n>=1000000000000000) 	ans+=n-999999999999999;
   cout<<ans;
   return 0;
}

D

#include <bits/stdc++.h>
using namespace std;

struct bag
{
	int w;
	int v;
	int id;
}a[60],box[60];

bool cmp1(bag x,bag y)
{
	return x.v>y.v;
}

bool cmp2(bag x,bag y)
{
	return x.w<y.w;
}

int n,m,q;
bool vis[60];

int main()
{
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++) cin>>a[i].w>>a[i].v;
	for(int i=1;i<=m;i++)
	{
		cin>>box[i].w;
		box[i].id=i;
	}
	
	sort(a+1,a+n+1,cmp1);
	sort(box+1,box+1+m,cmp2);
	
	while(q--)
	{
		int ans=0,l,r;
		cin>>l>>r;
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++)
		 for(int j=1;j<=m;j++)
		 {
		 	if(box[j].id>=l&&box[j].id<=r) continue;
		 	
		 	if(!vis[j]&&a[i].w<=box[j].w)
		 	{
		 		ans+=a[i].v;
		 		vis[j]=true;
		 		break;
			 }
		 }
		
	   cout<<ans<<endl;
	}
	return 0;
}