题解 | #有序序列判断#

#include <stdio.h>

int main() {
    int t;
    scanf("%d",&t);
    int prev = 0;
    int cur = 0;
    int flag = 1;
    int tmp = 0;
    for(int i=0;i<t;i++)
    {
        scanf("%d",&cur);
        if(i==1){
            tmp = cur-prev;
        }
        else{
            int prevf = tmp >> 31;
            tmp = cur-prev;
            int curf = tmp >> 31;
            if(!(prevf==0&&curf==0||prevf&&curf))
            {
                printf("unsorted\n");
                flag = 0;
                break;
            }
        }
        prev = cur;
    }
    if(flag) printf("sorted\n");
    return 0;
}

解题思路:

序列有序 可以是单调递增 也可以是单调递减

那么就只用将相邻元素的增量保存起来 下一次计算增量时比较与这个增量的符号 如果都是为正/负 则说明单调性仍然成立, 如果符号一正一负 那么单调性将不再成立 结束循环

那么怎么知道上次的增量与这次的增量符号是否相同呢,这里可以根据补码的性质,正数符号位为0,负数符号位为1,0和0与得到0,0和1与得到0, 1和1与得到1, 那么我们首先判断是否两个符号位都为0 如果是这种情况 那么也是单调性成立 除此之外 如果两个符号位相与结果为0 那么就说明单调性不成立 退出循环