P10679 『STA – R6』spec
题目描述
定义一个实数
α
\\alpha
α 的谱
Spec
(
α
)
\\operatorname{Spec}(\\alpha)
Spec(α) 是整数组成的一个无限长的序列
⌈
α
⌉
−
1
,
⌈
2
α
⌉
−
1
,
⌈
3
α
⌉
−
1
,
⋯
\\lceil\\alpha\\rceil-1,\\lceil2\\alpha\\rceil-1,\\lceil3\\alpha\\rceil-1,\\cdots
⌈α⌉−1,⌈2α⌉−1,⌈3α⌉−1,⋯。例如，
3
5
\\frac35
53 的谱的开头部分是
0
,
1
,
1
,
2
,
2
,
3
,
4
,
⋯
0,1,1,2,2,3,4,\\cdots
0,1,1,2,2,3,4,⋯。
现在给定
n
n
n 个整数
x
1
,
⋯
,
x
n
x_1,\\cdots,x_n
x1,⋯,xn，你要找到最大的实数
α
\\alpha
α，使得对于每个元素
x
i
x_i
xi 都有
x
i
x_i
xi 在
Spec
(
α
)
\\operatorname{Spec}(\\alpha)
Spec(α) 中出现过。
输入格式
第一行一个正整数
n
n
n。
第二行
n
n
n 个正整数
x
1
,
x
2
,
⋯
,
x
n
x_1,x_2,\\cdots,x_n
x1,x2,⋯,xn。
输出格式
一行，表示最大的
α
\\alpha
α。你的答案与标准答案的绝对误差低于
10
−
5
10^{-5}
10−5 即判为正确。
输入输出样例 #1
输入 #1
3
1 2 3
输出 #1
1.3333333
输入输出样例 #2
输入 #2
3
2 4 7
输出 #2
2.5000000
说明/提示
本题采用捆绑测试。
数据范围：
- Subtask 0 (10pts)：
n
,
x
i
≤
100
n,x_i\\le 100
n,xi≤100。 - Subtask 1 (15pts)：合法答案构成一段连续区间。
- Subtask 2 (25pts)：每个
x
i
x_i
xi 都是 2 的非负整数次幂。 - Subtask 3 (50pts)：无特殊限制。
对于全部数据，
1
≤
n
,
x
i
≤
1000
1\\le n,x_i\\le 1000
1≤n,xi≤1000。
C++实现
#include<bits/stdc++.h>
using namespace std;
int a[10000];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
n=unique(a+1,a+1+n)–a–1;
double opt=double(a[n]+1)/n;
for(;opt>=0;opt-=0.00000100) {
int r=1,l=1;
while((int)(ceil(opt*r*1.0000000)–1)<=a[l]&&l<=n) {
if((int)(ceil(opt*r*1.0000000)–1)==a[l])l++;
r++;
} if(l>n) {
printf("%.7f",opt);
return 0;
}
}
return 0;
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
