• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

TheZealous的赛前水题日常之 洛谷 P1068 [NOIP2009 普及组] 分数线划定(排序+模拟)

开发技术 开发技术 5小时前 2次浏览

【题目】

戳这里

 

【审题】

1.取前floor(m*1.50)个最大的之后还要带上与第floor(m*1.50)个分数相同的元素

2.相同成绩,id小的靠前

 

【分析】

1.对成绩和编号进行排序,成绩按逆序排序

2.排序后第floor(m*1.50)个人的成绩一定是基准线

3.从第floor(m*1.50)+1个人开始枚举,找出与第floor(m*1.50)个人成绩相同的人数sum

4.输出前sum+floor(m*1.50)个人的成绩

 

【代码实现】

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 struct stu
 5 {
 6     int id,gra;
 7 }a[10005];
 8 bool cmp(stu a,stu b)
 9 {
10     if(a.gra==b.gra) return a.id<b.id;
11     else return a.gra>b.gra;
12 }
13 int main()
14 {
15     scanf("%d %d",&n,&m);
16     m=(int)m*1.5;
17     for(int i=1;i<=n;i++)
18     {
19         scanf("%d%d",&a[i].id,&a[i].gra);
20     }
21     sort(a+1,a+1+n,cmp);
22     int sum=0;
23     printf("%d ",a[m].gra);
24     for(int i=m+1;i<=n;i++)
25     {
26         if(a[i].gra==a[m].gra) sum++;//这里之前写的计数方式问题很大,还是经yinz提点才明白没有必要每次和前一个元素比较,基准值直接设为a[m].gra即可
27         else break;
28         }
29     printf("%dn",sum+m);
30     for(int i=1;i<=sum+m;i++)
31     {
32         printf("%d %dn",a[i].id,a[i].gra);
33     }
34     return 0;
35 }

喜欢 (0)