| 题目名称 | 2491. 天才ACM |
|---|---|
| 输入输出 | geniusacm.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 LGLJ
于2019-10-22加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：14， 提交：59， 通过率：23.73% | ||||
 reØreOré |
100 | 0.914 s | 15.06 MiB | C++ |
 LGLJ |
100 | 0.978 s | 5.33 MiB | C++ |
 遥时_彼方 |
100 | 1.234 s | 12.59 MiB | C++ |
|
┭┮﹏┭┮ |
100 | 1.298 s | 10.31 MiB | C++ |
|
Theresis |
100 | 1.300 s | 15.15 MiB | C++ |
|
yrtiop |
100 | 1.315 s | 8.05 MiB | C++ |
|
op_组撒头屯 |
100 | 1.345 s | 8.83 MiB | C++ |
|
LGLJ |
100 | 1.483 s | 19.39 MiB | C++ |
|
00000 |
100 | 1.515 s | 8.83 MiB | C++ |
 增强型图元文件 |
100 | 1.523 s | 8.83 MiB | C++ |
| 关于 天才ACM 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回头看一下，这道题其实是一个相当经典的倍增 + 二分的模型，在 CTT2019 D1T2 也有考。不过再看到这个模型完全反应不过来。。
yrtiop
2024-02-18 22:57
3楼
| ||||
|
记得开longlong
 ┭┮﹏┭┮
2022-08-21 12:35
2楼
| ||||
|
倍增大法好！！！
ムラサメ
2021-09-28 21:24
1楼
| ||||
Genius ACM
【题目描述】
给定一个整数 $M$，对于任意一个整数集合 $S$，定义“校验值”如下:
从集合 $S$ 中取出 $M$ 对数(即 $2∗M$ 个数，不能重复使用集合中的数，如果 $S$ 中的整数不够 $M$ 对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大值就称为集合 $S$ 的“校验值”。
现在给定一个长度为 $N$ 的数列 $A$ 以及一个整数 $T$。
我们要把 $A$ 分成若干段，使得每一段的“校验值”都不超过 $T$。
求最少需要分成几段。
【输入格式】
第一行输入整数 $K$，代表有 $K$ 组测试数据。
对于每组测试数据，第一行包含三个整数 $N,M,T$。
第二行包含 $N$ 个整数，表示数列$A_1,A_2…A_N$。
【输出格式】
对于每组测试数据，输出其答案，每个答案占一行。
【样例输入】
2 5 1 49 8 2 1 7 9 5 1 64 8 2 1 7 9
【样例输出】
2 1
【数据规模】
$1≤K≤12$
$1≤N,M≤500000$
$0≤T≤10^{18}$
$0≤Ai≤2^{20}$
【来源】
《算法竞赛进阶指南》