#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 40001
#define K 5
#define M 101
using namespace std;
struct people{
int ge,gi,fg;
int id;
int chioce[K];
int rank;
}stu[N];
struct school{
int student[K];
int sum;
int need;
}sch[M];
int n,m,k;
bool cmp(people a,people b)
{
if(a.fg!=b.fg)
return a.fg>b.fg;
else return a.ge>b.ge;
}
bool cmp2(int a,int b)
{
return stu[a].id<stu[b].id;
}
void init()
{
int i;
for(i=0;i<m;i++)
sch[i].sum=0;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
init();
int i;
for(i=0;i<m;i++)
scanf("%d",&sch[i].need);
for(i=0;i<n;i++)
{
scanf("%d%d",&stu[i].ge,&stu[i].gi);
stu[i].id=i;
int j;
for(j=0;j<k;j++)
scanf("%d",&stu[i].chioce[j]);
stu[i].fg=stu[i].ge+stu[i].gi;
}
sort(stu,stu+n,cmp);
for(i=0;i<n;i++)
{
if(i>0&&stu[i].fg==stu[i-1].fg&&stu[i].ge==stu[i-1].ge)
stu[i].rank=stu[i-1].rank;
else stu[i].rank=i;
}
for(i=0;i<n;i++)
{
int j;
for(j=0;j<k;j++)
{
int z=stu[i].chioce[j];
int num=sch[z].sum;
int last=sch[z].student[num-1];
if(num<sch[z].need||stu[last].rank==stu[i].rank)
{
sch[z].student[num]=i;
sch[z].sum++;
break;
}
}
}
for(i=0;i<m;i++)
if(sch[i].sum==0)
printf("\n");
else
{
int j;
sort(sch[i].student,sch[i].student+sch[i].sum,cmp2);
for(j=0;j<sch[i].sum-1;j++)
printf("%d ",stu[sch[i].student[j]].id);
printf("%d\n",stu[sch[i].student[j]].id);
}
return 0;
}
一个节点运行超时,于是我就改
据说用ios::sync_with_stdio(false)会快
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 40001
#define K 5
#define M 101
using namespace std;
struct people{
int ge,gi,fg;
int id;
int chioce[K];
int rank;
}stu[N];
struct school{
int student[K];
int sum;
int need;
}sch[M];
int n,m,k;
bool cmp(people a,people b)
{
if(a.fg!=b.fg)
return a.fg>b.fg;
else return a.ge>b.ge;
}
bool cmp2(int a,int b)
{
return stu[a].id<stu[b].id;
}
void init()
{
int i;
for(i=0;i<m;i++)
sch[i].sum=0;
}
int main()
{
ios::sync_with_stdio(0);
cin>>n>>m>>k;
init();
int i;
for(i=0;i<m;i++)
cin>>sch[i].need;
for(i=0;i<n;i++)
{
cin>>stu[i].ge>>stu[i].gi;
stu[i].id=i;
int j;
for(j=0;j<k;j++)
cin>>stu[i].chioce[j];
stu[i].fg=stu[i].ge+stu[i].gi;
}
sort(stu,stu+n,cmp);
for(i=0;i<n;i++)
{
if(i>0&&stu[i].fg==stu[i-1].fg&&stu[i].ge==stu[i-1].ge)
stu[i].rank=stu[i-1].rank;
else stu[i].rank=i;
}
for(i=0;i<n;i++)
{
int j;
for(j=0;j<k;j++)
{
int z=stu[i].chioce[j];
int num=sch[z].sum;
int last=sch[z].student[num-1];
if(num<sch[z].need||stu[last].rank==stu[i].rank)
{
sch[z].student[num]=i;
sch[z].sum++;
break;
}
}
}
for(i=0;i<m;i++)
if(sch[i].sum==0)
cout<<endl;
else
{
int j;
sort(sch[i].student,sch[i].student+sch[i].sum,cmp2);
for(j=0;j<sch[i].sum-1;j++)
cout<<stu[sch[i].student[j]].id<<" ";
cout<<stu[sch[i].student[j]].id<<endl;;
}
return 0;
}
结果还是超时!!!!!!!!!!!!!!!!!!!!!
改了一万遍了,不晓得到底是哪里超时了,