P1583 魔法照片
#include <bits/stdc++.h>
using namespace std;
struct qz
{
int w;
int d,c;
int l;
} x[20200];
int cmp(const qz &a,const qz &b)//cmp函数写一个即可
{
if(a.w!=b.w)
return a.w>b.w;
else
return a.d<b.d;
}
int main()
{
int n,k;
cin>>n>>k;
int e[15];
for(int i=0; i<10; i++)
cin>>e[i];
for(int i=0; i<n; i++)
{
x[i].d=i+1;//题目有点绕,输入时自带序号
cin>>x[i].w;
}
sort(x,x+n,cmp);
/*for(int i=0; i<n; i++)
cout<<x[i].w<<" ";
cout<<endl;*/
for(int i=0; i<n; i++)
{
x[i].l=i+1;//额外成绩分组按照排序后的序号来
x[i].c=(x[i].l-1)%10+1;
x[i].w=x[i].w+e[x[i].c-1];
//cout<<x[i].d<<" "<<x[i].c<<" "<<x[i].w<<endl;
}
sort(x,x+n,cmp);
for(int i=0; i<k; i++)
cout<<x[i].d<<" ";
return 0;
}
P1051 谁拿了最多奖学金
#include <bits/stdc++.h>
using namespace std;
struct stu
{
string name;
int qm,bj,lw;
char gb,xb;
int id;
int mon=0;
} x[120];
int cmp(const stu &a,const stu &b)
{
if(a.mon!=b.mon)
return a.mon>b.mon;
else
return a.id<b.id;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>x[i].name>>x[i].qm>>x[i].bj>>x[i].gb>>x[i].xb>>x[i].lw;
x[i].id=i;
}
for(int i=0;i<n;i++)
{
if(x[i].qm>80&&x[i].lw>=1)
x[i].mon=x[i].mon+8000;
if(x[i].qm>85&&x[i].bj>80)
x[i].mon=x[i].mon+4000;
if(x[i].qm>90)
x[i].mon=x[i].mon+2000;
if(x[i].qm>85&&x[i].xb=='Y')
x[i].mon=x[i].mon+1000;
if(x[i].bj>80&&x[i].gb=='Y')
x[i].mon=x[i].mon+850;
}
sort(x,x+n,cmp);
int res=0;
for(int i=0;i<n;i++)
res=res+x[i].mon;
cout<<x[0].name<<endl<<x[0].mon<<endl<<res;
return 0;
}
P1093 奖学金
#include <bits/stdc++.h>
using namespace std;
struct stu
{
int yw,sx,yy,zf;
int id;
} x[320];
int cmp(const stu &a,const stu &b)
{
if(a.zf!=b.zf)
return a.zf>b.zf;
else if(a.yw!=b.yw)
return a.yw>b.yw;
else
return a.id<b.id;
}
int main()
{
int n;
cin>>n;
for(int i=0; i<n; i++)
{
cin>>x[i].yw>>x[i].sx>>x[i].yy;
x[i].zf=x[i].yw+x[i].sx+x[i].yy;
x[i].id=i+1;
}
sort(x,x+n,cmp);
for(int i=0;i<5;i++)
cout<<x[i].id<<" "<<x[i].zf<<endl;
return 0;
}
P1309 瑞士轮
最初的解决方法,每次就算新的s值,接下来进行快速排序
结果是超时
#include <bits/stdc++.h>
using namespace std;
struct stu
{
long long int s,w;
long long int id;
} x[200050];
int cmp(const stu &a,const stu &b)
{
if(a.s!=b.s)
return a.s>b.s;
else
return a.id<b.id;
}
int main()
{
int n,r,q;
cin>>n>>r>>q;
n=n*2;
for(int i=0; i<n; i++)
{
cin>>x[i].s;
x[i].id=i+1;
}
for(int i=0; i<n; i++)
cin>>x[i].w;
sort(x,x+n,cmp);
for(int a=0; a<r; a++)
{
for(int i=1; i<n; i=i+2)
{
if(x[i].w>x[i-1].w)
x[i].s++;
else
x[i-1].s++;
}
sort(x,x+n,cmp);
}
cout<<x[q-1].id;
return 0;
}
接下来是优化算法