牛客国庆集训派对Day1: K. Tengen Toppa Gurren Lagann（贪心）

69 阅读 0 评论 46 点赞

我是靠谱客的博主机智日记本，最近开发中收集的这篇文章主要介绍牛客国庆集训派对Day1: K. Tengen Toppa Gurren Lagann（贪心），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

K. Tengen Toppa Gurren Lagann

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 1048576K，其他语言2097152K
64bit IO Format: %lld

题目描述

Kamina正在为从世界各地集结而来的Ganmen(一种战斗机器人）军团整队。
Kamina麾下一共有 n 台Ganmen，每台Ganmen有一个互不相同的编号，编号的范围是 [1, n] 。Kamina命令 n 台Ganmen排成了一列，并决定委托Simon将这个序列分成 k 段，每段是一个小组。Kamina希望在每个小组内部按照编号升序排序之后，整个序列是递增的，为了增大成功率，他允许Simon在分好段之后任意地交换其中的两段，这个操作不是必须的，且最多进行一次。
现在，Simon希望知道他是否有可能完成这个任务。

输入描述:

第一行包括两个正整数 n (1 ≤ n ≤ 1000000)和 k (1 ≤ k ≤ n)。
第二行包括 n 个正整数 a1, a2, ..., an，数据保证 a 是一个1至n的排列。ai表示第i个Ganmen的编号。

输出描述:

一行，如果有解输出“Yes”，无解输出“Poor Simon”，不包括引号。

输入

10 3
10 9 8 7 5 6 4 3 2 1

输出

Yes

输入保证是个全排列

设L[k]表示前k个元素的最大值，F[l，r]表示区间[l，r]最多能分成多少段满足每一段排完序后整体升序（不能交换），sort(l，r)表示对区间[l，r]进行排序后的结果

很容易想到：F[1，n]等于满足L[k] = k的k的个数

而这题可以交换最多一次，那么肯定是当前F[1，n]段中的其中一段再拆成多段，并且交换第一段和最后一段后，结果最优

也就是说，只需要暴力枚举当前每一段，然后对于当前这一段[l，r]

先求出所有的临界点p满足sort(p+1，r)和sort(l，p)连接后整体升序
之后对于所有相邻的临界点p1, p2，很显然可以将前缀[l，p1]和后缀[p2+1，r]作为单独两段，并交换这两段后整体升序
这样这一段就可以被拆成2+F[p1+1，p2]段

这样的话对于当前段[l，r]，最多就能再拆成max(2+F[p1+1，p2])段（其中p1≠l，p2≠r，注意特判）

求出最大值和k比较一下就好了

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<string>
#include<math.h>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
#define LL long long
#define mod 1000000007
int a[1000005], b[1000005], L[1000005], L2[1000005], L3[1000005];
int Check(int l, int r, int bas)
{
	int i, sum;
	sum = L3[l-1] = 0;
	for(i=l;i<=r;i++)
	{
		L3[i] = max(L3[i-1], b[i]);
		if(L3[i]-bas==i-l)
			sum++;
	}
	return sum;
}
int Jud(int l, int r)
{
	int i, n, last, ans;
	n = r-l+1;
	for(i=1;i<=n;i++)
		b[i] = a[l+i-1]-l+1;
	last = 1, ans = 1;
	for(i=1;i<=n;i++)
	{
		L2[i] = min(L2[i-1], b[i]);
		if(i==1)
			L2[i] = b[i];
		if(n-L2[i]+1==i)
		{
			if(last==1 && i==n)
				continue;
			if(last==1 || i==n)
				ans = max(ans, 2);
			else
				ans = max(ans, Check(last, i, n-i+1)+2);
			last = i+1;
		}
	}
	return ans;
}
int main(void)
{
	int n, k, i, ans, last, sum;
	scanf("%d%d", &n, &k);
	ans = sum = 0;
	for(i=1;i<=n;i++)
	{
		scanf("%d", &a[i]);
		L[i] = max(L[i-1], a[i]);
		if(L[i]==i)
			sum++;
	}
	last = 1;
	for(i=1;i<=n;i++)
	{
		if(L[i]==i)
		{
			ans = max(ans, Jud(last, i)+sum-1);
			last = i+1;
		}
	}
	if(ans>=k)
		printf("Yesn");
	else
		printf("Poor Simonn");
	return 0;
}
/*
10 6
10 9 8 7 4 5 6 3 2 1
5 2
4 1 5 2 3
6 3
1 5 6 2 3 4
*/