洛谷 P6704 [COCI2010-2011#7] GITARA

[COCI2010-2011#7] GITARA

题目链接：https://www.luogu.com.cn/problem/P6704

题目背景

Darko 有一个想象的外星朋友，他有十亿根手指。外星人快速拿起吉他，在网上找到一段简单的旋律并开始弹奏。

这个吉他像寻常一样有六根弦，令其用 $1$ 到 $6$ 表示。每根弦被分成 $P$ 段，令其用 $1$ 到 $P$ 表示。

旋律是一串的音调，每一个音调都是由按下特定的一根弦上的一段而产生的（如按第 $4$ 弦第 $8$ 段）。如果在一根弦上同时按在几段上，产生的音调是段数最大的那一段所能产生的音调。

例：对于第 $3$ 根弦，第 $5$ 段已经被按，若你要弹出第 $7$ 段对应音调，只需把按住第 $7$ 段，而不需放开第 $5$ 段，因为只有最后的一段才会影响该弦产生的音调(在这个例子中是第 $7$ 段)。类似，如果现在你要弹出第 $2$ 段对应音调，你必须把第 $5$ 段和第 $7$ 段都释放。

请你编写一个程序，计算外星人在弹出给定的旋律情况下，手指运动的最小次数。

题目描述

你有一个 $6\times P$ 的矩阵 $A$，初始状态皆为 $0$。

对于所有要求 $(i,j)$

你需要满足要求：

1. 此时 $A_{i,j}$ 状态为 $1$。

2. 对于 $A_{i,j+k}(k>0)$ 状态为 $0$。

你在满足要求的情况下需要求状态转换最小次数。

输入格式

第一行包含两个正整数 $n$ ，$P$。它们分别指旋律中音调的数量及每根弦的段数。

下面的 $n$ 行每行两个正整数 $i$ ，$j$，分别表示能弹出对应音调的位置——弦号和段号，其为外星人弹奏的顺序。

输出格式

一个非负整数表示外星人手指运动次数最小值。

样例 #1

样例输入 #1

5 15
2 8
2 10
2 12
2 10
2 5

样例输出 #1

7

样例 #2

样例输入 #2

7 15
1 5
2 3
2 5
2 7
2 4
1 5
1 3

样例输出 #2

9

提示

样例 1 解释

所有的音调都是由第二根弦产生的。首先按顺序按 $8$ $10$ $12$ （$count=3$）。然后释放第 $12$ 段（$count=4$）。最后，按下第 $5$ 段，释放第 $8$ $10$ 段 （$count=7$）。

样例 2 解释

对于每个操作，分别需要 $1$ $1$ $1$ $1$ $3$ $0$ $2$ 次手指运动。

数据规模及约定

按下或释放一段弦各计一次手指运动。弹弦不算手指的移动，而是一个弹吉他的动作。（指你不需要管他怎么弹的，只需要按就是啦，说不定他可以用超能力呀）

对于 $100\%$ 的数据 $n\le 5\times 10^5$ ，$2\le P\le 3\times 10^5$

说明

本题满分 $70$ 分。

译自 COCI2010-2011 CONTEST #7 T3 GITARA

思路解析

有六根弦，每根弦只有最前面的一段发生，所以我们可以用六个栈来模拟六根弦。

• 如果要按的段比当前最大的段要大就直接压栈
• 如果要按的段比当前最大的段要小，那么不断弹栈直到栈空或者没有比它小的段停止，判断当前段是否跟需要按得段一致，一致就不需要操作，比它小就需要压栈

非常无脑非常长的CODE

#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long

using namespace std;

const int N = 3000005, p = 300005;
int stk[8][N];
int n, P;
int t1 = -1;
int t2 = -1;
int t3 = -1;
int t4 = -1;
int t5 = -1;
int t6 = -1;

	
int main(){
	cin >> n >> P;
	
	int ans = 0;
	int i, j;
	while(n--){
		scanf("%d%d", &i, &j);
		if(i == 1){
			while(t1 > -1 && stk[1][t1] > j){
				t1--;
				ans++;
			}
			if(t1 == -1 || stk[1][t1] < j){
				stk[1][++t1] = j;
				ans++;
			}
		}else if(i == 2){
			while(t2 > -1 && stk[2][t2] > j){
				t2--;
				ans++;
			}
			if(t2 == -1 || stk[2][t2] < j){
				stk[2][++t2] = j;
				ans++;
			}
		}else if(i == 3){
			while(t3 > -1 && stk[3][t3] > j){
				t3--;
				ans++;
			}
			if(t3 == -1 || stk[3][t3] < j){
				stk[3][++t3] = j;
				ans++;
			}
		}else if(i == 4){
			while(t4 > -1 && stk[4][t4] > j){
				t4--;
				ans++;
			}
			if(t4 == -1 || stk[4][t4] < j){
				stk[4][++t4] = j;
				ans++;
			}
		}else if(i == 5){
			while(t5 > -1 && stk[5][t5] > j){
				t5--;
				ans++;
			}
			if(t5 == -1 || stk[5][t5] < j){
				stk[5][++t5] = j;
				ans++;
			}
		}else if(i == 6){
			while(t6 > -1 && stk[6][t6] > j){
				t6--;
				ans++;
			}
			if(t6 == -1 || stk[6][t6] < j){
				stk[6][++t6] = j;
				ans++;
			}
		}
	}
	cout << ans << endl;
} 

代码虽然 $AC$，但是显得特别sb，复用很多不优雅不美观，但是想不到怎么优化，于是看了题解，果然还是题解大神nb啊，用数组存了栈顶指针，大大节省了代码量，tql，%%%%%%%%，果然还是我太菜了 <_>

巨佬的简短CODE

#include<iostream>
#include<cstdio>
using namespace std;
int n,p,x,y,s,sum[7],a[7][300005];
int main()
{
	scanf("%d%d",&n,&p);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		while(sum[x]>=1&&a[x][sum[x]]>y)//判断栈是否空，还有比较栈顶
		{
			sum[x]--;//减减
			s++;//累加次数	
		}
		if(a[x][sum[x]]==y)continue;//如果与栈顶相同就跳过
		a[x][++sum[x]]=y;//入栈
		s++;//累加次数
	} 
	printf("%d",s);//输出次数
	return 0;
} 

来源：https://blog.csdn.net/weixin_45524309/article/details/108541871