CVBB ACM Team

--- 2020-2021:teams:manespace:codeforces_round_656_div._3 [2020/07/24 11:41]
intouchables
+++ 2020-2021:teams:manespace:codeforces_round_656_div._3 [2020/07/24 11:43] (当前版本)
intouchables [C]
@@ 行 87: / 行 87: @@
   *题意：定义“good”序列：每次从首位或末位拿出元素，组成的新序列单调不降。多组数据，给定序列，询问删去从首位开始的至少多少元素，可以使序列成为“good”序列？
-  *题解：
+  *题解：所谓“good”序列就是从首末开始到某一位置都单调不降的序列，只需倒序遍历，先找不降序列，由此后找不升序列，统计剩余元素个数输出即可
 <hidden ac代码>
 <code c++>
+#include<bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+const int maxn = 2e5 + 5;
+const double pi = acos(-1);
+const int mod = 998244353;
+int t;
+int n;
+int a[maxn];
+int main(){
+	cin >> t;
+	while(t--){
+		cin >> n;
+		for(int i = 1; i <= n; ++i) cin >> a[i];
+		if(n == 1){
+			cout << 0 << endl;
+			continue;
+		}
+		int p = -1, q = -1;
+		for(int i = n; i > 1; --i){
+			if(a[i-1] < a[i]){
+				p = i;
+				break;
+			}
+		}
+		if(p == -1){
+			cout << 0 << endl;
+			continue;
+		}
+		for(int i = p; i > 1; --i){
+			if(a[i-1] > a[i]){
+				q = i;
+				break;
+			}
+		}
+		if(q == -1) cout << 0 << endl;
+		else cout << q - 1 << endl;
+	}
+}
 </code>
 </hidden>