A.神仙题
这题的名字就是我的感受
亲身经历，警钟敲烂，\(\mathtt{hash(\ )}\) 在 \(\mathtt{c++}\) 中是一个 \(\mathtt{STL}\) 函数。
不要重名！不要重名！！不要重名！！！
Solution
- 题解说是一个 \(\mathtt{O(n)}\) 的算法
然而我没有看懂，不过我用 \(\mathtt{O(n)}\) 外加一个 \(\mathtt{hash}\) 过了；
AC code
#include<bits/stdc++.h>
using namespace std;
#define re register
inline int read(){
re int s=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
s=s*10+int(ch-'0');
ch=getchar();
}
return s*f;
}
const int N=1e6+3;
int T,n;
int a[N+10];
int num[N+10];
int q[N+10],l=0;
inline int h(int x){
re int t=x%N;
while(a[t] && a[t]!=x)
(++t)%=N;
if(!a[t]) q[++l]=t;
a[t]=x;
return t;
}
int main(){
freopen("god.in","r",stdin);
freopen("god.out","w",stdout);
T=read();
while(T--){
n=read();
l=0;
int x,y;
int ans=-1;
for(re int i=1;i<=n;++i){
x=read();
if(ans>-1) continue;
y=h(x);
++num[y];
if(num[y]>(n>>1))
ans=x;
}
printf("%d\n",ans);
for(int i=1;i<=l;++i)
a[q[i]]=num[q[i]]=0;
}
return 0;
}
B.搬砖比赛
Solution
- 建一个小根堆，比如使用优先队列模拟，然后每次取队头就行了；
AC code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
s=s*10+int(ch-'0');
ch=getchar();
}
return s*f;
}
const int N=1e5+10;
#define re register
int n,T,W;
int tot=0,k=0;
struct memr{
int t,w;
bool operator<(const memr &_)const{
return t>_.t;
}
}a[N];
priority_queue<int>q;
int main(){
freopen("move.in","r",stdin);
freopen("move.out","w",stdout);
n=read();
T=read(),W=read();
for(re int i=1;i<n;++i){
a[i].t=read(),a[i].w=read();
if(a[i].t>T)
q.push(-(a[i].w-a[i].t+1));
}
sort(a+1,a+n);
re int l=1;
while(a[l].t>T && l<n)
++l;
int rk=q.size()+1;
int ans=rk;
while(T && q.size()){
int x=-q.top();
q.pop();
if(T<x) break;
T-=x;
--rk;
while(a[l].t>T && l<n){
q.push(-(a[l].w-a[l].t+1));
++l,++rk;
}
ans=min(ans,rk);
}
printf("%d",ans);
return 0;
}