这是一题开错的题
想法
每次两个人去最优(莫名悲伤),其中一个预算大于实际花费,另一个随意
理由如下
如果两个人去花费超过了预算,此时添加第三个人(他的花费小于预算),那么那个要别人钱的人可以润了
为了保证能去的次数尽量多,一个可以额外消费的人劲量把另一个超出消费的人拉上
只需要一个是为了保证后面额外消费的人能选到一个超出消费的人
而当超出消费的人不能进入餐厅时,只需要将剩下没去过餐厅的能额外消费的人两两分配即可
代码如下
#include <bits/stdc++.h>
using namespace std;
int a[100050],g[100050],f[100050];
bool cmp(int x,int y){return x>y;}
bool cmp1(int x,int y){return x<y;}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,l(0),r(0);
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
a[i]=x-a[i];
if (a[i]>=0) l++,f[l]=a[i];
else r++,g[r]=a[i];
}
sort(f+1,f+1+l,cmp);
sort(g+1,g+1+r,cmp1);
int j(1),ans(0);
for (int i=1;i<=l;i++)
{
while (g[j]+f[i]<0&&j<=r) j++;
if (j > r) ans=ans+((l-i+1)/2),i=l+1;
else j++,ans++;
}
printf("%d\n",ans);
}
return 0;
}
标签:消费,return,报告,1729D,++,int,解题,ans,100050
From: https://www.cnblogs.com/by-w/p/16719563.html