2020 CCPC 秦皇岛 E.Exam Results @ Wings            分类 ACM
发布于 星期五, 十二月 11 日, 2020 年
更新于 星期二, 七月 20 日, 2021 年

题目

题意

$T$组测试. $n$个学生参加考试. 如果第$i$个学生发挥得好, 他可以得$a_i$分; 否则他只能得$b_i$分. 一场考试结束后, 设最高分为$x$, 及格线为$x \cdot p$%. 问可能最多有几个学生及格.

$1 \le T \le 5 \cdot 10^3, 1 \le n \le 2 \cdot 10^5, 1 \le p \le 100, 1 \le b_i \le a_i \le 10^9$

题解

枚举最高分的时候, 应该对分数进行从大到小的顺序排序, 然后依次考虑, 考虑过的分数是不能选的.

那么既然要枚举最高分, 那么一定得把$n$个学生"拆"开, 一共$2n$个分数. 这样才可以枚举最高分.

每个学生都至少需要一个分数, 所以一但在枚举的过程中发现同一个学生的两个分数都枚举过了, 那么直接结束, 即枚举完第一个出现的$b$结束.

我们需要维护$[i, pos]$中学生的个数. 注意到$x$和$x \cdot p$% 都是单调的, 那么只需要维护一个滑动窗口即可. 具体来说: 维护一个数组 vis[] , 表示学生在窗口内出现的次数. 和 tot , 表示窗口内学生总数.

  1. 尾指针拓展一个分数时, 找到对应的学生, 记录次数( vis[tail]++ ). 如果是第一次找到这学生( 修改前的vis[tail] == 0 ), 则窗口内学生总数加一( tot++ ). 不断拓展尾指针, 直到他不在及格线内( score[tail] < score[head] * p / 100 ).
  2. 头指针移除时, 找到对应学生, 减去次数( vis[head]-- ), 同理维护 tot .

复杂度$O(n)$

最后注意score[head] * p / 100, $a(b)$ 最大可为$10^9$, $p$最大为$100$, 直接乘就炸int啦!!!

我才不会告诉你因为这个细节vp时调了3个小时换了2种做法WA了9发, 而且当场还没一个人找到这个极其**的失误

代码
const int maxn = 2e5+10;

int t, n, p;
int a[maxn], b[maxn], vis[maxn];

struct Score {
	int num, flag, id;
	bool operator < (const Score &N) const {
		return num == N.num ? flag < N.flag : num > N.num;
	}
} score[maxn * 2];

int main() {
	scanf("%d", &t);
	for (int kase = 1; kase <= t; kase++) {
		scanf("%d%d", &n, &p);
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			scanf("%d%d", a + i, b + i);
			score[i] = Score{a[i], 0, i};
			score[i + n] = Score{b[i], 1, i};
			vis[i] = 0;
		}
		sort(score + 1, score + 1 + 2 * n);

		int tot = 0, tail = 1;
		for (int head = 1; head <= 2 * n; head++) {
			while (score[tail].num >= score[head].num * (p / 100.0)) {
				int id = score[tail].id;
				if (vis[id] == 0)
					tot++;
				vis[id]++;
				tail++;
			}
			ans = max(ans, tot);
			if (score[head].flag)
				break;
			int id = score[head].id;
			if (vis[id] == 1)
				tot--;
			vis[id]--;
		}
		printf("Case #%d: %d\n", kase, ans);
	}
	return 0;
}
留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球
  • 三阶速拧20s

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch