做网站费是多少,微信网站与响应式网站有哪些,网站建设实习心得,什么项目适合新手创业题目链接#xff1a;https://vjudge.net/problem/UVA-514
题目分析
题目的意思是给一个栈输入一系列数据#xff0c;在这个过程中可以出栈#xff0c;看能否达到某个结果。 刚开始我觉得这个情况好多#xff0c;因此不是用模拟#xff0c;而应该观察结果本身。对于结果中…题目链接https://vjudge.net/problem/UVA-514
题目分析
题目的意思是给一个栈输入一系列数据在这个过程中可以出栈看能否达到某个结果。 刚开始我觉得这个情况好多因此不是用模拟而应该观察结果本身。对于结果中某个元素x比他小的元素肯定已经入过栈了此时可能有两种去处
已经在结果里面了还在栈里面
对于1.只能说它比x 小而且在x的前面除此之外没有其他约束了。 对于2.那些比x小的元素在结果中的位置肯定在x的后面而且肯定是逆序排列。因为只能进栈一次而他们是从小到大进栈的必然是从大到小出栈的。如果不符合这个条件肯定就是非法情况。 我的思路就是检查每个元素后面比他小的元素是否是逆序的复杂度是O(n2)O(n^2)O(n2) UVa里面有时候要求最后有换行有时候又要求不能有空行真是让人摸不着头脑。。
AC代码
#include iostream
#include vector
#include dequeusing namespace std;int n;
vectorint arr;bool check_idx(int idx) {int x arr[idx];int minx x;for (int i idx 1; i n; i) {if (arr[i] x) {if (arr[i] minx) return false;minx arr[i];}}return true;
}bool check() {for (int i 0; i n; i) {if (!check_idx(i)) return false;}return true;
}bool first true;int main() {ios::sync_with_stdio(false);while (cin n n ! 0) {
// if (first) first false;
// else cout \n;arr.resize(n);while (cin arr[0] arr[0] ! 0) {for (int i 1; i n; i) cin arr[i];if (check()) cout Yes\n;else cout No\n;}cout \n;}return 0;
}
半年后再来写这道题还是想到了这种方法虽然想到了一个优化但是最坏的复杂度仍然是O(n^2)的。而且没有用函数封装导致代码丑了一些。 和上次一样在换行这里卡了UVa真恶心还卡换行。
//
// Created by Administrator on 2022/4/20.
//#include iostream
#include vector/** 当x进入B的时候C中都是比x小的元素A中都是比x大的元素。* 因为进入C的元素越来越大所以比x小的还未出现的元素肯定在C里面的而且是以倒序出现在x的后面。* 因此对于出站的每一个x判断后面比x小的元素是不是逆序的。如果是则为真以后访问到就不用再判断了如果出现一个假就不可能了*/using namespace std;templatetypename T
void print(const vectorT arr) {for (auto x : arr) cout x ;cout \n;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, t;vectorint arr;vectorbool illegal;bool fail;while (cin n n) {arr.resize(n);illegal.resize(n, false);while (cin t t) {for (int i 0; i n; i) illegal[i] false;arr.clear();arr.push_back(t);for (int i 1; i n; i) {cin t;arr.push_back(t);}//print(arr);fail false;for (int i 0; i n; i) {if (illegal[i]) continue;t arr[i];illegal[i] true;for (int j i 1; j n; j) {if (arr[j] arr[i]) {if (arr[j] t) {illegal[j] true;t arr[j];} else {fail true;break;}}}if (fail) break;}if (fail) cout No\n;else cout Yes\n;}cout \n;}return 0;
}更好的思路
看了一下书上了代码书上的代码真的丑写出这么晦涩的代码也是很厉害的发现是可以进行模拟的而且复杂度是O(n)O(n)O(n)如果题目有心刁难我上面的解法可能就会TLE。 模拟的思路就是刚开始肯定是按照从小到大的元素进栈如果我们结果中当前元素直接是这个入栈的元素那么再直接出栈否则就丢在栈里。如果不是当前入栈元素那么就和栈顶的元素比较如果也不是那就先入栈看看后面的元素还有没有希望如果所有元素都已经入栈了那就没希望了直接GG。
AC代码
#include iostream
#include vector
#include dequeusing namespace std;int n;
dequeint s;
vectorint arr;bool check() {int x 1;for (int i 0; i n; i) {if (arr[i] x) {x;continue;}if (!s.empty()) {if (s.back() arr[i]) {s.pop_back();continue;} else if (s.back() arr[i]) {return false;}}
// if (x arr[i]) return false;if (x n) {s.push_back(x);--i;} else {return false;}}return true;
}int main() {ios::sync_with_stdio(false);while (cin n n ! 0) {arr.resize(n);while (cin arr[0] arr[0] ! 0) {s.clear();for (int i 1; i n; i) cin arr[i];if (check()) cout Yes\n;else cout No\n;}cout \n;}
}
感觉这道题的数据很弱我刚才把s.clear()写到循环外面去了都AC了。。 添加了一个优化语句当栈顶元素比结果中的当前元素大时直接不可达原因是后面的元素肯定都比栈顶元素大。
