解题报告

http://blog.csdn.net/juncoder/article/details/38102391

对于给定的数组，取对数组中的一段进行翻转，问翻转后是否是递增有序的。

思路：

仅仅要找到最初递减的区域，记录区域内最大和最小的值，和区间位置。

然后把最大值与区间的下一个元素对照，最小值与区间上一个元素对照。

这样还不够，可能会出现两个或两个以上的递减区间，这样的情况直接pass，由于仅仅能翻转一次。

#include <iostream>
#include <cstdio>
#include <cstring>
#define inf 999999999999
#define LL long long
#define swap(x,y,t) ((t)=(x),(x)=(y),(y)=(t))
using namespace std;
LL num[100010];
int main()
{
    int n,i,j;
    while(cin>>n)
    {
        for(i=1; i<=n; i++)
            cin>>num[i];
        for(i=1; i<=n; i++)
        {
            if(num[i+1]<num[i])
                break;
        }
        num[n+1]=inf;
        if(i==n+1)
        {
            printf("1 1\n");
            continue;
        }
        int l,r;
        LL maxx=0,minn=inf;
        int t=i;
        for(; i<=n; i++)
        {
            if(maxx<num[i])
            {
                maxx=num[i];
                r=i;
            }
            if(minn>num[i])
            {
                l=i;
                minn=num[i];
            }
            if(num[i+1]>num[i])
                break;
        }
        int u=i;
        int q=0;
        for(; i<=n; i++)
        {
            if(num[i+1]<num[i])
            {
                q=1;
                printf("no\n");
                break;
            }
        }
        if(!q)
            if(num[u+1]>=maxx&&num[t-1]<minn)
            {
                printf("yes\n");
                if(l<r)
                    swap(l,r,q);
                printf("%d %d\n",r,l);
            }
            else printf("no\n");
    }
    return 0;
}

Sort the Array

time limit per test 1 second

memory limit per test 256 megabytes

input standard input

output standard output

Being a programmer, you like arrays a lot. For your birthday, your friends have given you an arrayaconsisting ofndistinctintegers.

Unfortunately, the size ofais too small. You want a bigger array! Your friends agree to give you a bigger array, but only if you are able to answer the following question correctly: is it possible to sort the arraya(in increasing order) by reversingexactly onesegment ofa? See definitions of segment and reversing in the notes.

Input

The first line of the input contains an integern(1 ≤ n ≤ 105) — the size of arraya.

The second line containsndistinct space-separated integers:a[1], a[2], ..., a[n](1 ≤ a[i] ≤ 109).

Output

Print "yes" or "no" (without quotes), depending on the answer.

If your answer is "yes", then also print two space-separated integers denoting start and end (start must not be greater than end) indices of the segment to be reversed. If there are multiple ways of selecting these indices, print any of them.

Sample test(s)

input

3
3 2 1

output

yes
1 3

input

4
2 1 3 4

output

yes
1 2

input

4
3 1 2 4

output

no

input

2
1 2

output

yes
1 1

Note

Sample 1. You can reverse the entire array to get[1, 2, 3], which is sorted.

Sample 3. No segment can be reversed such that the array will be sorted.

Definitions

A segment[l, r]of arrayais the sequencea[l], a[l + 1], ..., a[r].

If you have an arrayaof sizenand you reverse its segment[l, r], the array will become:

a[1], a[2], ..., a[l - 2], a[l - 1], a[r], a[r - 1], ..., a[l + 1], a[l], a[r + 1], a[r + 2], ..., a[n - 1], a[n].

优质内容筛选与推荐>>
1、生成静态文件的新闻系统核心代码
2、新的一片天地
3、svm分类器
4、UNP1:Linux下实现traceroute程序
5、构建ant编译的android工程

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

阅读

好看

已推荐到看一看

你的朋友可以在“发现”-“看一看”看到你认为好看的文章。

取消 推荐

我知道了

已取消，“好看”想法已同步删除

知道了

已推荐到看一看 和朋友分享想法

最多200字，当前共字 发送

已发送

朋友将在看一看看到

确定

分享你的想法...

取消

分享想法到看一看

确定

最多200字，当前共字

发送中

网络异常，请稍后重试

知道了

微信扫一扫
关注该公众号

0 │ 收藏 │ 举报