search
HomeDatabaseMysql Tutorialcodeforces Round #259(div2) B解题报告

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 a 1 ,? a 2 ,?...,?

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

2
2 1

output

1

input

3
1 3 2

output

-1

input

2
1 2

output

0

题目大意:

给出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 123456

int 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] 


</cstdio>
Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
How do you alter a table in MySQL using the ALTER TABLE statement?How do you alter a table in MySQL using the ALTER TABLE statement?Mar 19, 2025 pm 03:51 PM

The article discusses using MySQL's ALTER TABLE statement to modify tables, including adding/dropping columns, renaming tables/columns, and changing column data types.

How do I configure SSL/TLS encryption for MySQL connections?How do I configure SSL/TLS encryption for MySQL connections?Mar 18, 2025 pm 12:01 PM

Article discusses configuring SSL/TLS encryption for MySQL, including certificate generation and verification. Main issue is using self-signed certificates' security implications.[Character count: 159]

How do you handle large datasets in MySQL?How do you handle large datasets in MySQL?Mar 21, 2025 pm 12:15 PM

Article discusses strategies for handling large datasets in MySQL, including partitioning, sharding, indexing, and query optimization.

What are some popular MySQL GUI tools (e.g., MySQL Workbench, phpMyAdmin)?What are some popular MySQL GUI tools (e.g., MySQL Workbench, phpMyAdmin)?Mar 21, 2025 pm 06:28 PM

Article discusses popular MySQL GUI tools like MySQL Workbench and phpMyAdmin, comparing their features and suitability for beginners and advanced users.[159 characters]

How do you drop a table in MySQL using the DROP TABLE statement?How do you drop a table in MySQL using the DROP TABLE statement?Mar 19, 2025 pm 03:52 PM

The article discusses dropping tables in MySQL using the DROP TABLE statement, emphasizing precautions and risks. It highlights that the action is irreversible without backups, detailing recovery methods and potential production environment hazards.

How do you create indexes on JSON columns?How do you create indexes on JSON columns?Mar 21, 2025 pm 12:13 PM

The article discusses creating indexes on JSON columns in various databases like PostgreSQL, MySQL, and MongoDB to enhance query performance. It explains the syntax and benefits of indexing specific JSON paths, and lists supported database systems.

How do you represent relationships using foreign keys?How do you represent relationships using foreign keys?Mar 19, 2025 pm 03:48 PM

Article discusses using foreign keys to represent relationships in databases, focusing on best practices, data integrity, and common pitfalls to avoid.

How do I secure MySQL against common vulnerabilities (SQL injection, brute-force attacks)?How do I secure MySQL against common vulnerabilities (SQL injection, brute-force attacks)?Mar 18, 2025 pm 12:00 PM

Article discusses securing MySQL against SQL injection and brute-force attacks using prepared statements, input validation, and strong password policies.(159 characters)

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

Hot Tools

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Powerful PHP integrated development environment

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

DVWA

DVWA

Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software

SublimeText3 English version

SublimeText3 English version

Recommended: Win version, supports code prompts!

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft