codeforces Round #259(div2) B解题报告_html/css_WEB-ITnose
Jun 24, 2016 am 11:55 AM
B. Little Pony and Sort by Shift
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
One day, Twilight Sparkle is interested in how to sort a sequence of integers a1,?a2,?...,?an in non-decreasing order. Being a young unicorn, the only operation she can perform is a unit shift. That is, she can move the last element of the sequence to its beginning:
a1,?a2,?...,?an?→?an,?a1,?a2,?...,?an?-?1.Help Twilight Sparkle to calculate: what is the minimum number of operations that she needs to sort the sequence?
Input
The first line contains an integer n (2?≤?n?≤?105). The second line contains n integer numbers a1,?a2,?...,?an (1?≤?ai?≤?105).
Output
If it's impossible to sort the sequence output -1. Otherwise output the minimum number of operations Twilight Sparkle needs to sort it.
Sample test(s)
input
22 1
output
input
31 3 2
output
-1
input
21 2
output
题目大意:
给出N个数字,可以每一次将最后一个数字移动到最前面,要求最终状态是一个单调非递减的序列,求最少需要花多少次操作。如若无法达到目标则输出“-1"。
解法:
也是一道很easy的编程基础题,找出两队单调非递减序列,分别为1~x 和 x+1~y,判断这两队是否覆盖整串数字,且a[n]
更简单的一种做法就是,将a[1]~a[n]复制一遍,拓展到a[1]~a[2*n],然后在1 ~ 2*n里面找,是否有一串单调不递减的个数为n的序列。
代码:
#include <cstdio>#define N_max 123456int n, x, y, cnt;int a[N_max];void init() { scanf("%d", &n); for (int i = 1; i a[i+1]) { x = i; break; } if (x == n) y = n; else for (int i = x+1; i a[i+1]) { y = i; break; } if (x == n) printf("0\n"); else if (y == n && a[y] <p></p> </cstdio>

Artikel Panas

Alat panas Tag

Artikel Panas

Tag artikel panas

Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6
Alat pembangunan web visual

SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas

Kesukaran mengemas kini caching laman web akaun rasmi: Bagaimana untuk mengelakkan cache lama yang mempengaruhi pengalaman pengguna selepas kemas kini versi?

Bagaimana saya menggunakan atribut pengesahan borang html5 untuk mengesahkan input pengguna?

Bagaimana cara menambah kesan strok kepada imej PNG di laman web?

Apakah tujuan & lt; iframe & gt; Tag? Apakah pertimbangan keselamatan semasa menggunakannya?

Apakah implikasi keselamatan menggunakan iframes, dan bagaimana saya dapat mengurangkannya?

Apakah amalan terbaik untuk keserasian penyemak imbas dalam HTML5?

Bagaimana saya menggunakan html5 & lt; meter & gt; elemen untuk memaparkan data berangka dalam julat?

Bagaimana saya menggunakan html5 & lt; masa & gt; elemen untuk mewakili tarikh dan masa secara semantik?
