42 条题解
-
3
猫粮寸断 LV 10 @ 2017-11-06 16:12:13
VIJOS数据比较水，用sort卡一个点，stable_sort就全过，然而在洛谷上会被卡，正解应该是归并排序
可以知道，每一轮比赛后都会有胜者组和败者组，每一组的要么都加1，要么都不变，因此胜者组和败者组仍各自是有序的，这样我们就可以O(n)的进行归并排序
贴代码#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct node { int num,s,w; }q[200010]; struct node1 { int num,s,w; }win[100010]; struct node2 { int num,s,w; }lose[100010]; int cmp(const node&x,const node&y) { if(x.s>y.s) return 1; if(x.s<y.s) return 0; return x.num<y.num; } int main() { int n,r,p,i,len1,len2; scanf("%d%d%d",&n,&r,&p); for(i=1;i<=2*n;i++) scanf("%d",&q[i].s); for(i=1;i<=2*n;i++) { q[i].num=i; scanf("%d",&q[i].w); } sort(q+1,q+2*n+1,cmp); while(r) { for(i=1;i<=n;i++) if(q[2*i].w>q[2*i-1].w) { q[2*i].s++; win[i].num=q[2*i].num; win[i].s=q[2*i].s; win[i].w=q[2*i].w; lose[i].num=q[2*i-1].num; lose[i].s=q[2*i-1].s; lose[i].w=q[2*i-1].w; } else { q[2*i-1].s++; win[i].num=q[2*i-1].num; win[i].s=q[2*i-1].s; win[i].w=q[2*i-1].w; lose[i].num=q[2*i].num; lose[i].s=q[2*i].s; lose[i].w=q[2*i].w; } len1=1; len2=1; while(len1<=n&&len2<=n) { if(win[len1].s>lose[len2].s) { q[len1+len2-1].num=win[len1].num; q[len1+len2-1].s=win[len1].s; q[len1+len2-1].w=win[len1].w; len1++; } if(win[len1].s<lose[len2].s) { q[len1+len2-1].num=lose[len2].num; q[len1+len2-1].s=lose[len2].s; q[len1+len2-1].w=lose[len2].w; len2++; } if(win[len1].s==lose[len2].s) if(win[len1].num<lose[len2].num) { q[len1+len2-1].num=win[len1].num; q[len1+len2-1].s=win[len1].s; q[len1+len2-1].w=win[len1].w; len1++; } else { q[len1+len2-1].num=lose[len2].num; q[len1+len2-1].s=lose[len2].s; q[len1+len2-1].w=lose[len2].w; len2++; } } while(len1<=n) { q[len1+len2-1].num=win[len1].num; q[len1+len2-1].s=win[len1].s; q[len1+len2-1].w=win[len1].w; len1++; } while(len2<=n) { q[len1+len2-1].num=lose[len2].num; q[len1+len2-1].s=lose[len2].s; q[len1+len2-1].w=lose[len2].w; len2++; } r--; } printf("%d",q[p].num); return 0; }-
dfdgfg568 @ 2018-03-24 11:33:35
受到dalao的启发才想到用归并排序，不过我写的比你简单一点。其实建一个结构体就行了，也不用一项项的赋值，一条等式就搞定了，还有ELSE语句的运用...不过我的程序比你的慢一点
状态 耗时 内存占用
#1 Accepted 2ms 2.363 MiB
#2 Accepted 4ms 2.34 MiB
#3 Accepted 4ms 2.375 MiB
#4 Accepted 18ms 2.488 MiB
#5 Accepted 37ms 4.5 MiB
#6 Accepted 48ms 2.73 MiB
#7 Accepted 85ms 3.375 MiB
#8 Accepted 167ms 4.965 MiB
#9 Accepted 180ms 5.0 MiB
#10 Accepted 184ms 4.969 MiB#include<bits/stdc++.h> using namespace std; struct player { int s,w,num; }a[200005],win[100005],lose[100005]; bool cmp(const player &x,const player &y) { if (x.s==y.s) return x.num<y.num; return x.s>y.s; } int main() { int n,r,q; int i,w,l; int lenw,lenl; cin>>n>>r>>q; n=n*2; for (i=1;i<=n;i++) cin>>a[i].s; for (i=1;i<=n;i++) cin>>a[i].w; for (i=1;i<=n;i++) a[i].num=i; sort(a+1,a+n+1,cmp); while (r>0) { lenw=0; lenl=0; for (i=1;i<=n;i=i+2) { if(a[i].w>a[i+1].w) { a[i].s++; win[++lenw]=a[i]; lose[++lenl]=a[i+1]; } else { a[i+1].s++; win[++lenw]=a[i+1]; lose[++lenl]=a[i]; } } w=1; l=1; i=1; while (w<=lenw&&l<=lenl) { if ((win[w].s>lose[l].s)||(win[w].s==lose[l].s&&win[w].num<lose[l].num)) { a[i]=win[w]; w++; } else { a[i]=lose[l]; l++; } i++; } while (w<=lenw) { a[i]=win[w]; w++; i++; } while (l<=lenl) { a[i]=lose[l]; l++; i++; } r--; } cout<<a[q].num; return 0; }
-
-
2
嘛，模拟加排序，为什么难度是7呢2333，虽然犯了好几个脑残错误导致WA了好几次（sort貌似不会超时吧。。。我试了一下sort最后一个点800ms
#include<iostream> #include<algorithm> using namespace std; typedef struct Member{ int ability; int score; int num; }Member; Member member[200050]; bool cmp(const Member& a,const Member& b){ if (a.score==b.score) return a.num<b.num; else return a.score>b.score; } void Rank(int n){ stable_sort(member,member+2*n,cmp); } void compare(int a,int b){ if(member[a].ability>member[b].ability){ member[a].score++; } else{ member[b].score++; } return; } int main(void){ int n,r,q; scanf("%d%d%d",&n,&r,&q); for(int i=0;i<2*n;i++){ scanf("%d",&member[i].score); member[i].num=i; } for(int i=0;i<2*n;i++){ scanf("%d",&member[i].ability); } Rank(n); for(int i=0;i<r;i++){ for(int j=0;j<2*n;j+=2){ compare(j,j+1); } Rank(n); } cout<<member[q-1].num+1<<endl; } -
2
jerryzheng2005 LV 10 @ 2017-05-27 22:17:48
//p1771 #include<iostream> #include<vector> #include<algorithm> using namespace std; struct player { int num,score,quality; }; int n,r,q; vector<player> a; bool cmp(const player& a,const player& b) { if (a.score==b.score) return a.num<b.num; return a.score>b.score; } void round() { for (int i=0;i<2*n;i+=2) if (a[i].quality>a[i+1].quality) a[i].score++; else a[i+1].score++; sort(a.begin(),a.end(),cmp); } int main() { int i,t; player temp; cin>>n>>r>>q; for (i=0;i<2*n;i++) { cin>>t; temp.num=i; temp.score=t; a.push_back(temp); } for (i=0;i<2*n;i++) { cin>>t; a[i].quality=t; } sort(a.begin(),a.end(),cmp); for (i=0;i<r;i++) round(); cout<<a[q-1].num+1<<endl; return 0; } -
1
aph。 (chenqianrong) LV 10 @ 2021-08-21 12:17:57
#include<bits/stdc++.h> using namespace std; int n,k,q,s; struct st{ int num; int grade; int shili; }; st a[210000],b[105000],c[105000]; int read() { int x=0; char s=getchar(); while(s>'9' || s<'0') s=getchar(); while(s<='9' && s>='0') x=x*10+s-'0',s=getchar(); return x; } bool cmp(st a1,st a2) { if(a1.grade!=a2.grade) return a1.grade>a2.grade; else return a1.num<a2.num; } void work() { int lb=0,lc=0,la; for(int i=1; i<n*2; i+=2){ if(a[i].shili>a[i+1].shili){ a[i].grade++; b[++lb]=a[i]; c[++lc]=a[i+1]; } else{ a[i+1].grade++; b[++lb]=a[i+1]; c[++lc]=a[i]; } } lb=1,lc=1,la=1; while(lb<=n && lc<=n){ if(cmp(b[lb],c[lc])) a[la++]=b[lb++]; else a[la++]=c[lc++]; } while(lb<=n) a[la++]=b[lb++]; while(lc<=n) a[la++]=c[lc++]; } int main() { n=read(),k=read(),q=read(); for(int i=1; i<=n*2; i++){ a[i].num=i; a[i].grade=read(); } for(int i=1; i<=n*2; i++) a[i].shili=read(); sort(a+1,a+n*2+1,cmp); for(int i=1; i<=k; i++) work(); cout<<a[q].num; return 0; } -
1
归并排序，速度更快
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<iostream> using namespace std; struct person{ int score; int num; int ability; person& operator = (const person&p){ score = p.score; num = p.num; ability = p.ability; return *this; } bool operator < (const person&p){ //小于表示排在前面，下同 if(score>p.score) return true; else if(score==p.score&&num<p.num) return true; return false; } } p[200005],win[100005],lose[100005]; int n,r,q; int main(){ scanf("%d%d%d",&n,&r,&q); for(int i=0;i<2*n;i++){ scanf("%d",&p[i].score); p[i].num = i+1; } for(int i=0;i<2*n;i++){ //输入实力值 scanf("%d",&p[i].ability); } sort(p,p+2*n); for(int i=0;i<r;i++){ for(int j=0;j<n;j++){ if(p[2*j].ability > p[2*j+1].ability){ p[2*j].score++; win[j] = p[2*j]; lose[j] = p[2*j+1]; }else{ p[2*j+1].score++; win[j] = p[2*j+1]; lose[j] = p[2*j]; } } int wj=0,lj=0; while(wj<n&&lj<n){ if(win[wj]<lose[lj]) p[wj+lj]=win[wj],wj++; else p[wj+lj]=lose[lj],lj++; } if(wj==n) for(;lj<n;lj++) p[wj+lj]=lose[lj]; else for(;wj<n;wj++) p[wj+lj]=win[wj]; } cout<<p[q-1].num; return 0; } -
1
普通的sort，一开始还用了优先队列，结果发现贼慢，直接用数组就险AC了。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<iostream> #include<vector> #include<queue> #include<map> using namespace std; bool cmp(pair<int,int> a,pair<int,int> b){ if(a.first>b.first) return true; else if(a.first==b.first&&a.second<b.second) return true; return false; } int n,r,q,cap[200005]; pair<int,int> p[200005],a,b; int main(){ scanf("%d%d%d",&n,&r,&q); for(int i=0;i<2*n;i++){ scanf("%d",&p[i].first); p[i].second = i+1; } sort(p,p+2*n,cmp); for(int i=1;i<=2*n;i++){ //输入实力值 scanf("%d",cap+i); } for(int i=0;i<r;i++){ for(int j=0;j<n;j++){ p[2*j].first += (cap[p[2*j].second]>cap[p[2*j+1].second]) ; p[2*j+1].first += (cap[p[2*j].second]<cap[p[2*j+1].second]); } sort(p,p+2*n,cmp); } cout<<p[q-1].second; return 0; } -
1
#include<iostream>
#include<algorithm>
using namespace std;
struct matcher{
int ID,score,power;
matcher(int i,int s,int p)
{
ID=i;
score=s;
power=p;
}
matcher()
{
matcher(0,0,0);
}
};
struct cmp{
bool operator() (matcher a,matcher b)
{
if(a.score==b.score) return a.ID<b.ID;
else return a.score>b.score;
}
};
int n,r,q;
matcher mats[200001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>r>>q;
for(int i=1;i<=2*n;i++)
{
cin>>mats[i].score;
mats[i].ID=i;
}
for(int i=1;i<=2*n;i++)
{
cin>>mats[i].power;
}
stable_sort(mats+1,mats+2*n+1,cmp());
for(int i=0;i<r;i++)
{
for(int j=0;j<=2*n;j+=2)
{
if(mats[j].power >= mats[j-1].power) mats[j].score++;
else mats[j-1].score++;
}
stable_sort(mats+1,mats+2*n+1,cmp());
}
cout<<mats[q].ID;
return 0;
} -
1
#1 Accepted 7ms 256.0 KiB
#2 Accepted 1ms 256.0 KiB
#3 Accepted 1ms 256.0 KiB
#4 Accepted 26ms 384.0 KiB
#5 Accepted 61ms 764.0 KiB
#6 Accepted 174ms 1.25 MiB
#7 Accepted 395ms 2.469 MiB
#8 Accepted 551ms 4.855 MiB
#9 Accepted 776ms 4.375 MiB
#10 Accepted 998ms 4.75 MiB
这个。。。算巧合吗 -
1
#include<bits/stdc++.h>
using namespace std;
int N,n,R,Q,win[100001],lose[100001],wini,losei,ki;
struct node
{
int s,w,num;
}f[200001],k[200001];
bool cmp(node a,node b)
{
return a.s>b.s ||(a.s==b.s && a.num<b.num);
}
int gi()
{
int x=0;char ch=getchar();
while(ch<'0' || ch>'9')ch=getchar();
while(ch>='0' && ch<='9')x=x*10+ch-48,ch=getchar();
return x;
}
int main()
{
N=gi();n=N*2;R=gi();Q=gi();
for(int t=1;t<=n;t++)
{
f[t].s=gi();
f[t].num=t;
}
for(int t=1;t<=n;t++)
{
f[t].w=gi();
}
sort(f+1,f+n+1,cmp);
while(R--)
{
wini=losei=1;
for(int tt=1;tt<=n;tt+=2)
{
if(f[tt].w>f[tt+1].w)f[tt].s+=1,win[wini++]=tt,lose[losei++]=tt+1;
else f[tt+1].s+=1,win[wini++]=tt+1,lose[losei++]=tt;
}
wini=losei=ki=1;
while(wini<=N && losei<=N)
{
if((f[win[wini]].s>f[lose[losei]].s) || (f[win[wini]].s==f[lose[losei]].s && f[win[wini]].num<f[lose[losei]].num))
k[ki++]=f[win[wini++]];
else k[ki++]=f[lose[losei++]];
}
while(wini<=N)
k[ki++]=f[win[wini++]];
while(losei<=N)
k[ki++]=f[lose[losei++]];
for(int ii=1;ii<=n;ii++)
f[ii]=k[ii];
}
printf("%d",f[Q].num);
return 0;
} -
1
larryzhong LV 9 @ 2017-05-11 13:28:08
其实，c++ 的 stl 中的 sort() 并不是不可以 (可能是 O2). 注意 n 要乘以 2, 以及排序和开数组.
c++ AC:#include <iostream> #include <algorithm> using namespace std; const int maxn = 200010; int w[maxn]; struct player { int id, s; bool operator < (const player &other) const { // 很重要! return s > other.s || (s == other.s && id < other.id); } } a[maxn]; int main() { ios::sync_with_stdio(false); // 很重要! int n, r, q; cin >> n >> r >> q; n *= 2; // 很重要! for (int i = 0; i < n; i++) { a[i].id = i; cin >> a[i].s; } for (int i = 0; i < n; i++) cin >> w[i]; sort(a, a + n); for (int i = 0; i < r; i++) { for (int j = 0; j < n; j += 2) a[j + (w[a[j].id] < w[a[j+1].id])].s++; sort(a, a + n); } cout << a[q - 1].id + 1 << endl; return 0; } -
1
#include <iostream> #include <stdlib.h> #include <stdio.h> #include <algorithm> using namespace std; struct anode { int fenshu; int shili; int bianhao; }; bool cmp(const anode &x, const anode &y) { if(x.fenshu!=y.fenshu){return x.fenshu>y.fenshu;} else{return x.bianhao<y.bianhao;} } int main() { int n,r,q; cin>>n>>r>>q; anode a[200050]; for(int i=1;i<=2*n;i++) { scanf("%d",&a[i].fenshu); a[i].bianhao=i; } for(int i=1;i<=2*n;i++){scanf("%d",&a[i].shili);} //__________________________________________________ for(int j=1;j<=r;j++) { stable_sort(a+1,a+1+2*n,cmp); for(int i=1;i<=2*n-1;i=i+2) { if(a[i].shili<a[i+1].shili){a[i+1].fenshu++;} else{a[i].fenshu++;} } } stable_sort(a+1,a+1+2*n,cmp); //___________________________________________________ printf("%d",a[q].bianhao); return 0; } 使用cincout 或者sort()都会挂2个点 应该用scanfprintf 和 stable_sort() -
0
asd393814041 LV 10 @ 2022-01-26 18:16:02
#include<cstdio>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
struct node
{
int id,score;
}a[200010];
bool cmp(node a,node b)
{
if(a.score==b.score)
return a.id<b.id;
else
return a.score>b.score;
}
int main()
{
int n,r,q,power[200010];
cin>>n>>r>>q;
for(int i=1;i<=2*n;i++)
{
cin>>a[i].score;
a[i].id=i;
}
for(int i=1;i<=2*n;i++)
cin>>power[i];
sort(a+1,a+1+2*n,cmp);
for(int i=1;i<=r;i++)
{
for(int j=1;j<=n;j++)
{
if(power[a[2*j-1].id]>power[a[2*j].id])
a[2*j-1].score++;
else
a[2*j].score++;
}
sort(a+1,a+1+2*n,cmp);
}
cout<<a[q].id;
return 0;
} -
0
#include<iostream>
#include<algorithm>
using namespace std;
struct matcher{
int ID,score,power;
matcher(int i,int s,int p)
{
ID=i;
score=s;
power=p;
}
matcher()
{
matcher(0,0,0);
}
};
struct cmp{
bool operator() (matcher a,matcher b)
{
if(a.score==b.score) return a.ID<b.ID;
else return a.score>b.score;
}
};
int n,r,q;
matcher mats[200001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>r>>q;
for(int i=1;i<=2*n;i++)
{
cin>>mats[i].score;
mats[i].ID=i;
}
for(int i=1;i<=2*n;i++)
{
cin>>mats[i].power;
}
stable_sort(mats+1,mats+2*n+1,cmp());
for(int i=0;i<r;i++)
{
for(int j=0;j<=2*n;j+=2)
{
if(mats[j].power >= mats[j-1].power) mats[j].score++;
else mats[j-1].score++;
}
stable_sort(mats+1,mats+2*n+1,cmp());
}
cout<<mats[q].ID;
return 0;
} -
0
#include<cstdio> #include<algorithm> struct player{ int num; int grade; int strength; }; int n, round, need; player a[200010], b[200010], ans[200010]; bool cmp(const player& a, const player& b){ if(a.grade==b.grade) return a.num<b.num; else return a.grade>b.grade; } void solve(){ int _a=1, _b=1; for(int i=1; i<=n*2; i+=2){ if(ans[i].strength>ans[i+1].strength){ ans[i].grade++; a[_a++]=ans[i]; b[_b++]=ans[i+1]; } else{ ans[i+1].grade++; a[_a++]=ans[i+1]; b[_b++]=ans[i]; } } int i=1, j=1, k=1; while(i<_a&&j<_b){ if(cmp(a[i], b[j])){ ans[k++]=a[i++]; } else ans[k++]=b[j++]; } while(i<_a) ans[k++]=a[i++]; while(j<_b) ans[k++]=b[j++]; } int main(){ scanf("%d%d%d", &n, &round, &need); for(int i=1; i<=n*2; i++){ scanf("%d", &ans[i].grade); ans[i].num=i; } for(int i=1; i<=n*2; i++){ scanf("%d", &ans[i].strength); } std::sort(ans+1, ans+2*n+1, cmp); for(int i=1; i<=round; i++) solve(); printf("%d", ans[need].num); return 0; } -
0
嗯，挺简单的，其实不难
Var n,r,q,i,cc,rs,k:longint; fs,sl,b:array[1..300000]of longint; sz,lz,szfs,lzfs,szsl,lzsl:array[1..300000]of longint; Procedure quicksort(l,r:longint); Var i,j,mid,t,bh:longint; Begin i:=l; j:=r; mid:=fs[(i+j) div 2]; bh:=b[(i+j) div 2]; repeat while (fs[i]>mid) or ((fs[i]=mid) and (b[i]<bh)) do inc(i); while (fs[j]<mid) or ((fs[j]=mid) and (b[j]>bh)) do dec(j); if i<=j then begin t:=fs[i]; fs[i]:=fs[j]; fs[j]:=t; t:=sl[i]; sl[i]:=sl[j]; sl[j]:=t; t:=b[i]; b[i]:=b[j]; b[j]:=t; inc(i); dec(j); end; until i>=j; if i<r then quicksort(i,r); if l<j then quicksort(l,j); End; Procedure hb; Var rs,lose,win,i:longint; Begin fillchar(b,sizeof(b),0); fillchar(fs,sizeof(fs),0); fillchar(sl,sizeof(sl),0); win:=1; lose:=1; rs:=0; while (win<=n) and (lose<=n) do begin inc(rs); if (szfs[win]>lzfs[lose]) or ((szfs[win]=lzfs[lose]) and (sz[win]<lz[lose])) then begin sl[rs]:=szsl[win]; fs[rs]:=szfs[win]; b[rs]:=sz[win]; inc(win); end else if (szfs[win]<lzfs[lose]) or ((szfs[win]=lzfs[lose]) and (sz[win]>lz[lose])) then begin sl[rs]:=lzsl[lose]; fs[rs]:=lzfs[lose]; b[rs]:=lz[lose]; inc(lose); end; end; if win<=n then begin rs:=win; for i:=n*2-(n-win+1)+1 to n*2 do begin sl[i]:=szsl[rs]; fs[i]:=szfs[rs]; b[i]:=sz[rs]; inc(rs); end; end; if lose<=n then begin rs:=lose; for i:=2*n-(n-lose+1)+1 to 2*n do begin sl[i]:=lzsl[rs]; fs[i]:=lzfs[rs]; b[i]:=lz[rs]; inc(rs); end; end; End; Begin //assign(input,'1.in');reset(input); readln(n,r,q); for i:=1 to n*2 do read(fs[i]); for i:=1 to n*2 do read(sl[i]); for i:=1 to n*2 do b[i]:=i; quicksort(1,n*2); cc:=0; while cc<r do begin inc(cc); k:=1; rs:=0; while k<=n*2 do begin if sl[k]>sl[k+1] then begin inc(rs); sz[rs]:=b[k]; szfs[rs]:=fs[k]+1; szsl[rs]:=sl[k]; lz[rs]:=b[k+1]; lzfs[rs]:=fs[k+1]; lzsl[rs]:=sl[k+1]; end else begin inc(rs); sz[rs]:=b[k+1]; szfs[rs]:=fs[k+1]+1; szsl[rs]:=sl[k+1]; lz[rs]:=b[k]; lzfs[rs]:=fs[k]; lzsl[rs]:=sl[k]; end; inc(k,2); end; hb; end; writeln(b[q]); readln; End. -
0
可以的，很完美的题目
sort最后一个点完美TLE，看大神题解说用stable_sort就能过
然后
就真的过了
最后一个点跑了600MS#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct player{ int num,goal,li; }q[200010]; int comp(const player&x,const player&y) { if(x.goal>y.goal) return 1; else if(x.goal<y.goal) return 0; else if(x.num>y.num) return 0; else return 1; } int main() { int n,r,m,i; cin>>n>>r>>m; for(i=1;i<=2*n;i++) scanf("%d",&q[i].goal); for(i=1;i<=2*n;i++) { scanf("%d",&q[i].li); q[i].num=i; } sort(q+1,q+2*n+1,comp); while(r--) { stable_sort(q+1,q+2*n+1,comp); for(i=1;i<=n;i++) { if(q[2*i].li>q[2*i-1].li) q[2*i].goal++; else q[2*i-1].goal++; } } sort(q+1,q+2*n+1,comp); cout<<q[m].num; return 0; } -
0
归并排序
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include <algorithm>
using namespace std;
int i,j,r,x,y,N,R,Q,temp1=0,temp2=0;
struct apple{
int no,score,w;
bool operator<(const apple &other)const{
return score>other.score || (score==other.score && no<other.no);
}
}s[300000],a1[200000],a2[200000];
int main(){
scanf("%d%d%d",&N,&R,&Q);
for(i=1;i<=2*N;i++){
s[i].no=i;
scanf("%d",&s[i].score);
}for(i=1;i<=2*N;i++)
scanf("%d",&s[i].w );sort(s+1,s+2*N+1);
for(i=1;i<=R;i++){
temp1=0;temp2=0;for(j=1;j<=N;j++){
int xx=j*2-1;
if(s[xx].w > s[xx+1].w ){
s[xx].score++;
a1[++temp1]=s[xx];
a2[++temp2]=s[xx+1];
}
else {
s[xx+1].score++;
a1[++temp1]=s[xx+1];
a2[++temp2]=s[xx];
}
}temp1=0;
x=1; y=1;
while(x<=N && y<=N){
if(a1[x].score>a2[y].score || (a1[x].score==a2[y].score && a1[x].no<a2[y].no))
{
s[++temp1]=a1[x];
x++;
}
else {
s[++temp1]=a2[y];
y++;
}
}
if(x<=N)
for(r=x;r<=N;r++)s[++temp1]=a1[r];
if(y<=N)
for(r=y;r<=N;r++)s[++temp1]=a2[r];}
printf("%d\n",s[Q].no);
return 0;
} -
0
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include <algorithm>
using namespace std;
int i,j,r,x,y,N,R,Q,temp1=0,temp2=0;
struct apple{
int no,score,w;
bool operator<(const apple &other)const{
return score>other.score || (score==other.score && no<other.no);
}
}s[300000],a1[200000],a2[200000];
int main(){
freopen("swiss10.in","r",stdin);
freopen("swiss.out","w",stdout);
scanf("%d%d%d",&N,&R,&Q);
for(i=1;i<=2*N;i++){
s[i].no=i;
scanf("%d",&s[i].score);
}for(i=1;i<=2*N;i++)
scanf("%d",&s[i].w );sort(s+1,s+2*N+1);
for(i=1;i<=R;i++){
temp1=0;temp2=0;for(j=1;j<=N;j++){
int xx=j*2-1;
if(s[xx].w > s[xx+1].w ){
s[xx].score++;
a1[++temp1]=s[xx];
a2[++temp2]=s[xx+1];
}
else {
s[xx+1].score++;
a1[++temp1]=s[xx+1];
a2[++temp2]=s[xx];
}
}temp1=0;
x=1; y=1;
while(x<=N && y<=N){
if(a1[x].score>a2[y].score || (a1[x].score==a2[y].score && a1[x].no<a2[y].no))
{
s[++temp1]=a1[x];
x++;
}
else {
s[++temp1]=a2[y];
y++;
}
}
if(x<=N)
for(r=x;r<=N;r++)s[++temp1]=a1[r];
if(y<=N)
for(r=y;r<=N;r++)s[++temp1]=a2[r];}
printf("%d\n",s[Q].no);
return 0;
} -
0
#1 Accepted 3ms 256.0KiB
#2 Accepted 3ms 256.0KiB
#3 Accepted 3ms 256.0KiB
#4 Accepted 29ms 384.0KiB
#5 Accepted 65ms 2.363MiB
#6 Accepted 172ms 996.0KiB
#7 Accepted 402ms 1.5MiB
#8 Accepted 528ms 2.625MiB
#9 Accepted 780ms 2.715MiB
#10 Accepted 954ms 2.594MiB
最后一点 954ms强行AC#include<cstdio> #include<iostream> #include<algorithm> #define MAXN 200010 using namespace std; int n,r,q; struct node { int w; int s; int id; }; node a[MAXN]; inline void read(int&x) { x=0;int f=1;char c=getchar(); while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-48;c=getchar();} x=x*f; } inline bool cmp(const node x,const node y) { if(x.s==y.s) return x.id<y.id; else return x.s>y.s; } int main() { read(n);read(r);read(q); for(int i=1;i<=n*2;i++) { a[i].id=i; read(a[i].s); } for(int i=1;i<=2*n;i++) read(a[i].w); sort(a+1,a+1+2*n,cmp); while(r--) { for(int i=1;i<=n*2;i+=2) { if(a[i].w>a[i+1].w) a[i].s++; else a[i+1].s++; } sort(a+1,a+1+2*n,cmp); } printf("%d\n",a[q].id); return 0; } -
0
Onlynagesha LV 9 @ 2017-01-29 20:23:10
类似归并排序的方法，时间复杂度O（RN）
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
#define rep(id,a,b) for(int id=(a);id<(b);++id)
#define irep(id,a,b) for(int id=(a);id>(b);--id)
#define reset(arr,c) memset(arr,c,sizeof(arr))typedef long long int64;
const int maxN=100000+5;
struct Player
{
int s,n,a;
void assign(int _s,int _n,int _a) { s=_s,a=_a,n=_n; }
bool operator > (const Player& other) const
{
return s > other.s || (s == other.s && n < other.n);
}
Player& operator = (const Player& other)
{
s=other.s,n=other.n,a=other.a;
return *this;
}
};Player win[maxN],lose[maxN];
Player all[maxN<<1];
int N,R,Q;void input()
{
scanf("%d%d%d",&N,&R,&Q);
rep(i,0,N<<1) all[i].n=i+1;
rep(i,0,N<<1) scanf("%d",&all[i].s);
rep(i,0,N<<1) scanf("%d",&all[i].a);
}#include <functional>
int solve()
{
sort(all,all+(N<<1),greater<Player>());
while(R--)
{
rep(i,0,N)
{
int w=(all[i<<1].a > all[(i<<1)|1].a)?(i<<1):(i<<1)|1;
win[i]=all[w],lose[i]=all[w^1];
++win[i].s;
}
int w=0,l=0;
while(w<N && l<N)
{
if(win[w]>lose[l]) { all[w+l]=win[w]; ++w; }
else { all[w+l]=lose[l]; ++l; }
}
if(w<N) rep(i,w,N) all[i+l]=win[i];
else rep(i,l,N) all[i+w]=lose[i];
}
return all[Q-1].n;
}int main() { input(); printf("%d\n",solve()); return 0; }
猫粮寸断
LV 10
@ 2017-11-06 16:12:13
