卡牌——蓝桥杯十三届2022国赛大学B组真题

样例输入

4 5
1 2 3 4
5 5 5 5

样例输出

3

样例说明

这 5 张空白牌中,拿2张写1,拿1张写2,这样每种牌的牌数就变为了3,3,3,4, 可以凑出 3套牌,剩下2张空白牌不能再帮助小明凑出一套。
评测用例规模与约定
对于30%的数据，保证n$⩽$ 2000;
对于100%的数据，保证n$⩽$ 2$\times 10^5$ ;$a_i,b_i⩽$ 2n;m$⩽$ n${}^2$.

运行限制

• 最大运行时间：1s
• 最大运行内村：521M

问题分析

可以想象成一个木桶问题：每张卡牌的a值实际上就是木桶的每一块木板的高度，而d值就是此块木板还能延长的长度，而输入的m就是现有的木料，该问题实际上就是问我应该如何合理使用我有的木料来延长木板使得木桶能装的水的高度最高。众所周知木桶能装的水取决于最短的那块木板，因此要尽量拔高木板的下限。

方法一

将所有卡牌按照a的大小从小到大依次排列，然后从左到右依次遍历，模拟此过程：若左边牌的牌数比下一张牌的牌数要少，我们要拔高下限，则就要使左边牌的牌数尽可能接近右边的牌数，最好相等，若相等，则继续往下遍历否则退出循环。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
struct node{//记录a值和b值
	int a,b;
	bool operator<(const node &nd)const{
		if(a!=nd.a)return a<nd.a;
		return b<nd.b;
	}
};
int main() {
	int n,ans,mind;//ans:最后的答案也就是所有牌数的下限，mind:左边牌的最小d，也就是左边牌还能一起每张增加的牌数
	LL m;
	cin>>n>>m;
	vector<node> vec(n);
	for(int i=0;i<n;i++){
		cin>>vec[i].a;
	}
	for(int i=0;i<n;i++){
		cin>>vec[i].b;
	}
	sort(vec.begin(),vec.end());//将每张牌排序
	ans=vec[0].a;//初始化
	mind=vec[0].b;
	int i=1;
	for(i=1;i<n;i++){
		if(vec[i].a!=vec[i-1].a){//如果左边牌数少于此牌的牌数
			if(vec[i-1].a+mind<vec[i].a||m<i*(vec[i].a-vec[i-1].a))break;//如果左边的牌数无法与此牌牌数相等则退出循环
			m-=i*(vec[i].a-vec[i-1].a);//m要减少i*(vec[i].a-vec[i-1].a)张牌:左边有i种牌，并且都与第i张牌的牌数差vec[i].a-vec[i-1].a张
			ans=vec[i].a;//更新左边牌平均数数
			mind-=(vec[i].a-vec[i-1].a);//更新最小d值
		}
		mind=min(mind,vec[i].b);//更新最小d值
	}
	ans+=min((int)(m/i),mind);//将最后剩余的牌均分给左边牌
	cout<<ans<<endl;
	return 0;
}

方法二

用优先队列每次从中选出a值最小的那种牌，然后给它手写一张，直到不能手写为止（d=0||m==0)

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 200010;
int n;
long long m;
int a[N],b[N];
int main()
{
  cin>>n>>m;
  priority_queue<PII,vector<PII>,greater<PII>> q;
  for(int i = 0;i<n;i++){
    cin>>a[i];
  }
  for(int i = 0;i<n;i++){
    cin>>b[i];
    q.push({a[i],b[i]});
  }
  while(m){
    auto t = q.top();
    if(t.y == 0){
      //不能再手写了
      break;
    }
    q.pop();
    t.x++;//a++
    t.y--;//d--
    m--;
    q.push({t.x,t.y});
  }
  cout<<q.top().x<<endl;
  return 0;
}