建模-判断一列数是不是等差数列

题目: 如果一个数列S满足对于所有的合法的i,都有S[i + 1] = S[i] + d, 这里的d也可以是负数和零,我们就称数列S为等差数列。 小易现在有一个长度为n的数列x,小易想把x变为一个等差数列。小易允许在数列上做交换任意两个位置的数值的操作,并且交换操作允许交换多次。但是有些数列通过交换还是不能变成等差数列,小易需要判别一个数列是否能通过交换操作变成等差数列。

输入要求: 输入包括两行,第一行包含整数n(2 ≤ n ≤ 50),即数列的长度;第二行n个元素x[i](0 ≤ x[i] ≤ 1000),即数列中的每个整数。

输出要求: 如果可以变成等差数列输出”Possible”,否则输出”Impossible”。

例如 输入: 3 3 1 2 输出: Possible

解题思路: 在各种各样的编程题中,有些是直接给出要求,比如从尾到头打印链表,我们只看题目就可以一抹了然,数据结构是链表,要求是从后向前打印。但是有时给的更像是一个应用题,这就好比小学时一个水管放水,一个水管注水的问题一样,好神奇…..这是网易的一道题目,说了半天就是要判断一列数字是不是等差数列,由于没有插入与删除操作,一个顺序存储结构就可以啦。 我们可以试着这样来解决,找到一列数(n个)中的最大max和最小min,如果max=min,则为公差为0的等差数列,如果不相等那么公差就是max-min/n-1,如果没办法除尽的话,那么不是等差数列,如果除尽,即求出公差error。 现在我们知道了一个数列的最大值,最小值,个数和公差,这样就知道了等差数列的每一个数,那么下面就可以逐个判断这些数是不是在数组中,由于不是排序的数组,二分法啥的也就用不了了,所以时间复杂度是O(n^2),那么有没有其他的方法可以优化时间复杂度呢? 由于我们知道数组中的最小值,那么如果是等差数列的话,数组中的每个数与最小值的差值,对error取模的结果应该都是0,这样我们就可以判断一列数是不是等差数列了,时间复杂度为O(n)。

代码实现:

#include "iostream"    
using namespace std;

int main()
{
    int str[50];
    int num;
    cin>>num;
    for (int i = 0;i<num;i++)
        cin>>str[i];
    int maxvalue =0;
    for (int i = 0;i<num;i++)
    {
        if (maxvalue<str[i])
          maxvalue=str[i];
    }
    int minvalue =maxvalue;
    for (int i = 0;i<num;i++)
    {
        if (minvalue>str[i])
            minvalue=str[i];
    }
    if (maxvalue==minvalue)
    {
        cout<<"Possible"<<endl ;
        return 0;
    }
    int flag =  (maxvalue-minvalue)%(num-1);
    if (flag != 0)
    {
            cout<<"Impossible"<<endl ;
            return 0;
    }
    int error =(maxvalue-minvalue)/(num-1);
    for (int j=0;j <num;j++)
    {
        if ((str[j]-minvalue)%error !=0)
            cout<<"Impossible"<<endl;
    }
    cout<<"Possible"<<endl;
    return 0;
}  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SeanCheney的专栏

《Pandas Cookbook》第07章 分组聚合、过滤、转换1. 定义聚合2. 用多个列和函数进行分组和聚合3. 分组后去除多级索引4. 自定义聚合函数5. 用 *args 和 **kwargs

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

1912
来自专栏jeremy的技术点滴

py3_cookbook_notes_01

3128
来自专栏racaljk

Julia体验 语言基础

以前听说过Julia,不过那时候官网还处于时不时宕机状态,最近Julia发布了1.0 released版本到处都是它的资讯,官网良心自带简体中文,趁着热度我也来...

1552
来自专栏菩提树下的杨过

java:POI导出excel

POI是一个开源项目,专用于java平台上操作MS OFFICE,企业应用开发中可用它方便导出Excel. 下面是使用示例: 1、maven中先添加依赖项 1 ...

2405
来自专栏草根专栏

用C#(.NET Core) 实现简单工厂和工厂方法设计模式

本文源自深入浅出设计模式. 只不过我是使用C#/.NET Core实现的例子. 前言 当你看见new这个关键字的时候, 就应该想到它是具体的实现. ? 这就是一...

5094
来自专栏算法修养

PAT 1010 Radix

1010. Radix (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 St...

3555
来自专栏数据结构与算法

codevs 1213 解的个数

1213 解的个数 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 已知整数x...

3324
来自专栏IT可乐

Java 枚举类 详解

1、枚举是什么?   Java中的枚举其实是一种语法糖,在 JDK 1.5之后出现,用来表示固定且有限个的对象。比如一个季节类有春、夏、秋、冬四个对象;一个星期...

1919
来自专栏mySoul

设计模式 里氏替换原则

在场景中,三毛需要什么枪支,就直接new 出一个枪支即可,然后其内通过抽象类获取到对象,然后对齐进行修饰

1036
来自专栏机器学习入门

挑战程序竞赛系列(86):3.6极限情况(3)

挑战程序竞赛系列(86):3.6极限情况(3) 传送门:AOJ 2201: Immortal Jewels 翻译参考至hankcs: http://www....

20610

扫码关注云+社区