神仙题
\(solution\)
快读+sort找出现次数大于n/2的编号就可以过了，时间限制是5s，考场没过是我想太多
AC Code
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int N=1e6+5;
int t,n,a[N];
int main()
{
// freopen("god.in","r",stdin);
// freopen("god.out","w",stdout);
t=read();
while(t--)
{
n=read();
for(int i=1;i<=n;i++)a[i]=read();
sort(a+1,a+n+1);
int cnt=0;
for(int i=1;i<=n;i++)
{
(a[i]==a[i-1])?cnt++:cnt=1;
if(cnt>n/2)
{
printf("%d\n",a[i]);
break;
}
}
}
return 0;
}
搬砖比赛
\(solution\)
优先队列建一个小根堆，把大于\(a_1\)的还能搬砖的最大重量扔进来，在和\(a_1\)比较一下，每次\(a_1\)大小减小都与之前答案比较看是否为最优
AC Code
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int N=1e5+5;
int n;
priority_queue<int>q;
struct ww{
int t,w;
}a[N];
bool cmp(ww x, ww y)
{
return x.t>y.t;
}
int main()
{
// freopen("move.in","r",stdin);
// freopen("move.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)
a[i].t=read(),a[i].w=read();
sort(a+2,a+n+1,cmp);
int tmp=2,ans=1,tmp2;
for(int i=tmp;i<=n;i++)
{
if(a[i].t>a[1].t)
{
ans++;
q.push(-a[i].w+a[i].t-1);
}
else
{
tmp=i;
break;
}
}
tmp2=ans;
while(q.size()&&a[1].t>0)
{
int u=-q.top();
if(u>a[1].t)break;
q.pop();a[1].t-=u;tmp2--;
for(int i=tmp;i<=n;i++)
{
if(a[i].t>a[1].t)
{
tmp2++;
q.push(-a[i].w+a[i].t-1);
}
else
{
tmp=i;
break;
}
}
ans=min(ans,tmp2);
}
printf("%d\n",ans);
return 0;
}