上海计算机学会2024年1月月赛C++乙组T2等差数列（二）
发布时间
阅读量：
阅读量
等差数列（二）
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定 n 个整数 a1,a2,...,an ，请你选出一个集合，使得集合内的数字可以组成等差数列。
请问所选集合最多可以包含多少个数字？
输入格式
输入共两行，
第一行：一个正整数 n
第二行：n 个整数 a1,a2,...,an
输出格式
输出共一个整数，表示所求答案。
数据范围
- 30% 的数据，1≤n≤20
- 60% 的数据，1≤n≤100
- 100% 的数据，1≤n≤1000 ，0≤ai≤10^9
样例数据
输入:
5
4 3 2 1 5
输出:
5
说明:
全选后可以构成1、2、3、4、5的等差数列
输入:
6
5 0 2 3 9 6
输出:
4
说明:
选0、3、6、9
解析：
先排序，然后枚举以ai开头的等差数列，枚举其后的每一个数，对于可能的公差，判断上一差值是否存在，若存在，数列数量加一，时间复杂度O（N^2根号N）；
终测只有80分，最后两个点超时了。
详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int a[1005];
int ans=0;
int main() {
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);//排序
for(int i=1;i<=n;i++){//枚举a[i]开头的等差数列
map<int,int> mp;
for(int j=i+1;j<=n;j++){//枚举a[i]后边的每一个数
int x=a[j]-a[i];//求差
if(x==0) mp[0]++;//公差为0的情况
for(int k=1;k*k<=x;k++){//枚举可能的公差k和x/k
if (x%k==0){//对于可能的公差
if (mp[k]==x/k-1){//如果上一差值存在
mp[k]++;//增加一个
}
if (mp[x/k]==k-1){//如果上一差值存在
mp[x/k]++;//增加一个
}
}
}
}
//求出最大值
for(auto p=mp.begin();p!=mp.end();p++){
ans=max(ans,p->second+1);
}
}
cout<<ans;
return 0;
}
AI写代码cpp
另一种解法：满分
#include<bits/stdc++.h>
using namespace std;
int n;
int a[1005];
int ans=0;
int main() {
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i+ans<=n;i++){//枚举数列第一个数字
for(int j=i+1;j+ans+1<=n;j++){//枚举数列第二个数字
int gc=a[j]-a[i];//公差
int cnt=2;//目前等差数列长度
int next=a[i]+gc*cnt;//等差数列下一个数
for(int k=j+1;k<=n;k++){//枚举剩下的数字
if (a[k]==next){//如果等于下一个数
cnt++;//等差数列数量增加一
next+=gc;//更新等差数列下一个数
}else if (a[k]>next){//如果大于等差数列下一个数
break;//后边的数也一定比下一个数大，没必要再找了
}
}
ans=max(ans,cnt);//取最大值
}
}
cout<<ans;
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~