每日一题
程序员文章站
2022-07-12 23:09:16
...
排序子序列
牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为n的整数数组A,他现在有一个任
务是把数组A分为若干段排序子序列,牛牛想知道他最少可以把这个数组分为几段排序子序列.
如样例所示,牛牛可以把数组A划分为[1,2,3]和[2,2,1]两个排序子序列,至少需要划分为2个排序子序列,所以输出2
输入描述:
输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)
第二行包括n个整数A_i(1 ≤ A_i ≤ 10^9),表示数组A的每个数字。
输出描述:
输出一个整数表示牛牛可以将A最少划分为多少段排序子序列
输入:
6
1 2 3 2 2 1
输出:
2
#include <iostream>
using namespace std;
#define N 100001
bool isChange(int previous, int current, int next) {
if ((current > previous && current > next) ||
(current < previous && current < next)) {
return true;
}
return false;
}
int main() {
int n, arr[N];
while (cin >> n) {
int ans = 1, previous = 0;
// 序列长度小于3,输出1
if (n < 3) cout << "1" << endl;
for (int i = 0; i < n; i++)
cin >> arr[i];
for (int i = 1; i < n - 1; i++) {
if (arr[i] == arr[i + 1]) {
continue;
}
else {
// 若发生跳变,计数+1,指针+1。
if (isChange(arr[previous], arr[i], arr[i + 1])) {
ans++;
previous = ++i;
}
}
}
cout << ans << endl;
}
return 0 ;
}
倒置字符串:
将一句话的单词进行倒置,标点不倒置。比如 I like beijing. 经过函数后变为:beijing. like I
输入描述:
每个测试输入包含1个测试用例: I like beijing. 输入用例长度不超过100
输出描述:
依次输出倒置之后的字符串,以空格分割
输入:
I like beijing.
输出:
beijing. like I
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main() {
string str;
stack<string> sta;
while(cin >> str) {
sta.push(str);
if(*(str.rbegin()) == '.') {
break;
}
}
cout << sta.top();
sta.pop();
while(!sta.empty()) {
cout << ' ' << sta.top();
sta.pop();
}
return 0;
}
上一篇: 每日一题 比例简化
下一篇: AcWing 458. 比例简化