玩遍所有游戏_牛客博客

题目描述:

游戏商城有n个小冯想玩的游戏，第i个游戏的价格为ci元。在最近一周里小冯在游戏商城逛了m次，第i次逛商城时，小冯有wi块钱。每次逛游戏商城小冯最多只能买1个游戏，每个游戏小冯最多只会买1次，那小冯最多能买多少个游戏呢？

输入：

输入共3行。
第1行输入2个整数n,m (1<=n,m<=10^5)

第2行输入n个整数
c1...cn, ci(1<=ci<=10^9)表示第i个物品的价格。

第3行输入m个整数
w1...wm, wi(1<=wi<=10^9)表示第i次进入游戏商城时ycf有多少钱。

输出：

输出一个整数，表示小冯最多能买多少个游戏。

样例输入：

15 20
4 3 9 10 7 7 5 3 6 1 8 6 6 1 5 
12 4 1 9 8 5 8 6 4 5 18 8 14 9 9 7 20 11 8 19

样例输出

思路：

因为逛了m次，每次最多买1个游戏，所以当m<n时，小冯最多能买m次
为了能买到最多的游戏，每次要买的最值，就是每次购买时在小冯能接受的程度下，购买最贵的那款游戏
二分找到在ci<=wi的最后一个游戏

代码部分：

第一次交的时候只过86%的数据（调试阶段）

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+100;
vector<int> a;// 每件游戏只能购买一次，那选完之后要进行删除，所以采用动态数组 
int main()
{
	int n,m,x;cin>>n>>m;
	int res=0;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		a.push_back(x); 
	}
	sort(a.begin(),a.end());

	for(int i=1;i<=m;i++)
	{
		int t;cin>>t;
		int l=0,r=n-1;
		while(l<r)
		{
			int mid=(l+r+1)/2;
			if(a[mid]<=t) l=mid;
			else r=mid-1;
		}
//  接下来三句是调试语句 提供参考
//		cout<<l<<endl;
//		cout<<r<<endl;
//		cout<<endl;
		if(a[r]<=t)
		{
			a.erase(a.begin()+r);// a.begin()+l是个迭代器 即删除位置为r点的数据 
			n--;
			res++;	
		}
	}
	cout<<res<<endl;
	return 0;
}

错误原因在29行的if语句的条件
因为测试样例的逛商城次数大于游戏的总个数所以在后面的二分中会出现r=-1的现象，即当r=-1时,a[r]<=t时答案错误
如图：

修改后AC的代码

using namespace std;
const int N=1e5+100;
vector<int> a;// 每件游戏只能购买一次，那选完之后要进行删除，所以采用动态数组 
int main()
{
	int n,m,x;cin>>n>>m;
	int res=0;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		a.push_back(x); 
	}
	sort(a.begin(),a.end());

	for(int i=1;i<=m;i++)
	{
		int t;cin>>t;
		int l=0,r=n-1;
		while(l<r)
		{
			int mid=(l+r+1)/2;
			if(a[mid]<=t) l=mid;
			else r=mid-1;
		}
		if(a[r]<=t&&r>=0)
		{
			a.erase(a.begin()+r);// a.begin()+l是个迭代器 即删除位置为r点的数据 
			n--;
			res++;	
		}
	}
	cout<<res<<endl;
	return 0;
}

希望大家可以点个小赞赞吧