timmy0226 @ 2024-10-13 14:02:05
T了…… 求思路与正解 感谢dalao们
by da_ke @ 2024-10-13 14:03:27
@timmy0226 https://www.luogu.com.cn/article/o7n2liv3
by _8008008 @ 2024-10-13 14:04:23
@timmy0226 排序，然后统计排名即可，排名定义是奖牌数量大于它的人的数量。
by timmy0226 @ 2024-10-13 14:05:46
题面： 有 n 个小朋友参加了若干场比赛，其中第 i 个小朋友获得了 g[i]枚金牌、 s[i]枚银牌和 b[i]枚铜牌。老师希望每个小朋友制作一张所有小朋友的排行榜。
然而小朋友们为了让自己的排名尽量靠前，自然是可以动一些小心思的，体现在排序标准上——每个小朋友可以选择按照金牌数从大到小排序，也可以选择按照银牌数从大到小排序，也可以选择按照铜牌数从大到小排序。在小朋友自制的排行榜里，如果自己和别的小朋友并列，那么他可以把自己写在最前面。
给出每个小朋友获得的金牌数、银牌数和铜牌数，请对于每个小朋友 i，计算他在他自己的排行榜里最好能排第几名。
by rpyluogu @ 2024-10-13 14:08:20
排序后每次询问二分。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int g[200005],s[200005],b[200005];
int gc[200005],sc[200005],bc[200005];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(register int i=1;i<=n;i++){
cin>>g[i]>>s[i]>>b[i];
gc[i]=g[i];
sc[i]=s[i];
bc[i]=b[i];
}
sort(g+1,g+n+1);
sort(s+1,s+n+1);
sort(b+1,b+n+1);
for(register int i=1;i<=n;i++){
int cnt=0,res=0,tot=0;
int ga=gc[i],sa=sc[i],ba=bc[i];
cnt=upper_bound(g+1,g+n+1,ga)-g-1;
res=upper_bound(s+1,s+n+1,sa)-s-1;
tot=upper_bound(b+1,b+n+1,ba)-b-1;
cnt=n-cnt+1;
res=n-res+1;
tot=n-tot+1;
cout<<min(cnt,min(res,tot))<<'\n';
}
}by timmy0226 @ 2024-10-13 14:12:43
谢谢各位dalao提供的思路，已关
by DGFLSzfd @ 2024-10-13 14:22:34
@timmy0226 无脑STL，排序后用map来记多少分排在第几名，虽然慢了一丢丢，但是无脑可以过 ，我10s就想出来了。
by timmy0226 @ 2024-10-13 17:18:58
@DGFLSzfd 谢谢思路，已关
by CNzzc @ 2024-10-13 17:51:36
@timmy0226 预处理所有选手按金、银、铜牌的名次，查询时求最小值
以972ms的时间卡过
记得关同步流
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define up(i,j,k,l) for(int i=j;i<=k;i+=l)
#define down(i,j,k,l) for(int i=j;i>=k;i-=l)
using namespace std;
const int N=2e5+10;
int n;
struct node{
int g,s,b,w;
};
node a[N];
int t[N][5],d,ct;
bool cmp1(node x1,node x2)
{
return x1.g>x2.g;
}
bool cmp2(node x1,node x2)
{
return x1.s>x2.s;
}
bool cmp3(node x1,node x2)
{
return x1.b>x2.b;
}
void solve()
{
cin>>n;
up(i,1,n,1){
cin>>a[i].g>>a[i].s>>a[i].b;
a[i].w=i;
}
sort(a+1,a+n+1,cmp1);
ct=1;
up(i,1,n,1){
d=i;
while(a[d].g==a[d+1].g && d+1<=n){
t[a[d].w][1]=ct;
d++;
}
t[a[d].w][1]=ct;
ct+=d-i+1;
i=d;
}
sort(a+1,a+n+1,cmp2);
ct=1;
up(i,1,n,1){
d=i;
while(a[d].s==a[d+1].s && d+1<=n){
t[a[d].w][2]=ct;
d++;
}
t[a[d].w][2]=ct;
ct+=d-i+1;
i=d;
}
sort(a+1,a+n+1,cmp3);
ct=1;
up(i,1,n,1){
d=i;
while(a[d].b==a[d+1].b && d+1<=n){
t[a[d].w][3]=ct;
d++;
}
t[a[d].w][3]=ct;
ct+=d-i+1;
i=d;
}
up(i,1,n,1){
cout<<min({t[i][1],t[i][2],t[i][3]})<<endl;
}
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
//freopen("medal3.in","r",stdin);
//freopen("CCC.out","w",stdout);
int _=1;
//cin>>_;
while(_--){
solve();
}
return 0;
}by timmy0226 @ 2024-10-14 14:09:41
@CNzzc 感谢，已关