我用递归写单调栈(?)_资讯

我用递归写单调栈(?)

创始人

2024-05-13 07:25:47

0次

在这里插入图片描述
前言：嗯,这个题上午有的思路，敲了一中午代码，改了一下午最后超时?
题：D. Boris and His Amazing Haircut
题意：一个理发师可以把一段数组给建成一个高度，他现在每个高度的剪子都有若干个。给一个原始数组和目标数组，问能不能剪成目标数组。
奇怪的想法： 理发师最优的剪法就是先剪出来高的，然后在高的头发形成的段之间再剪次高的。直接上分治，结果超时，边界控制太难写了，
超时的代码：

#include
#include
#include
#include
#include
using namespace std;
const int length = 2e5 + 5;
vector ag;
vector bg;
map mp;
vector count1;
vector> index1;
int tree[length << 3];
void update(int l, int r, int L, int R, int cnt, int v)
{if (L >= l && R <= r){tree[cnt] = v;return;}if (L > r || R < l){return;}int mid = (L + R) / 2;update(l, r, L, mid, cnt << 1, v);update(l, r, mid + 1, R, cnt * 2 + 1, v);tree[cnt] = max(tree[cnt * 2], tree[cnt * 2 + 1]);
}
int query(int l, int r, int L, int R, int cnt)
{if (L>=l&&R<=r){return tree[cnt];}if (L > r || R < l)return 0;int mid = (L + R) / 2;int a = query(l, r, L, mid, cnt * 2);int b = query(l, r, mid + 1, R, cnt * 2 + 1);return max(a, b);
}
int n1;
bool DP(int l, int r)
{//if()if (l > r)return 1;int yh = query(l, r, 0, n1 - 1, 1);bool sum = 1;int lflag = ((l==0)?0:1);int rflag = ((r==n1-1)?0:-1);int cut = 0;//找到第一个大于等于l的数int a = -1;int b = index1[yh].size();while (a != b - 1){int mid = (a + b) / 2;if (index1[yh][mid] < l)a = mid;elseb = mid;}int i = b;int in = 0;for (; iif (i != index1[yh].size() && mp[ag[index1[yh][i]]] != mp[bg[index1[yh][i]]]&&cut==0){cut = 1;if (count1[mp[bg[index1[yh][i]]]])count1[mp[bg[index1[yh][i]]]]--;elsereturn 0;}if (in == 0){bool a=DP(l , index1[yh][i] - 1);sum = sum & a;}else{bool a = DP(index1[yh][i - 1] + 1, index1[yh][i] - 1);sum = sum & a;}if (sum == 0)return sum;in = 1;}if (i!=index1[yh].size()&&index1[yh][i] > r){if (i != 0){bool a = DP(index1[yh][i - 1] + 1, r);sum = sum & a;}}else if (i == index1[yh].size() && index1[yh][i - 1] != r){bool a = DP(index1[yh][i - 1] + 1, r);sum = sum & a;}return sum;
}
int main(void)
{int t;scanf_s("%d", &t);for (int i = 0; i < t; i++){int n;scanf_s("%d", &n);n1 = n;vector a(n,0);for (int i = 0; i < n; i++){scanf_s("%d", &a[i]);}vector b(n, 0);for (int i = 0; i < n; i++){scanf_s("%d", &b[i]);}int m;scanf_s("%d", &m);vector c(m, 0);for (int i = 0; i < m; i++){scanf_s("%d", &c[i]);}ag = a; bg = b;//全局变量赋值vector tmp=b;sort(tmp.begin(), tmp.end());vector::iterator p = unique(tmp.begin(), tmp.end());int off = p - tmp.begin();map hk;int cnt = 1;for (int i = 0; i < off; i++){hk[tmp[i]] = i + 1;}mp = hk;vector tmp_count(length);for (int i = 0; i < m; i++){tmp_count[mp[c[i]]]++;//统计映射之后的数量}count1 = tmp_count;memset(tree, 0, sizeof(tree));vector> edge(length);int ok = 1;for (int i = 0; i < n; i++){if (a[i] < b[i])ok = 0;update(i, i, 0, n - 1, 1, mp[b[i]]);//更新区间最值以及坐标位置edge[mp[b[i]]].push_back(i);}if (ok == 0){printf("NO\n");continue;}index1 = edge;int yh=DP(0, n - 1);if (yh)printf("YES\n");elseprintf("NO\n");}
}

正解：
思考源头：为啥要剪一段？省剪子啊，他的剪子都是一次性的，用完不能再用乐。并且剪成高度为555的时候不能穿过高度为888的。所以就用单调栈呗，注意a[i]==b[i]a[i]==b[i]a[i]==b[i]的头发可以弹出数，但是不能入栈，入栈的目的就是不让两边相同高度的头发剪两次。但是a[i]==b[i]a[i]==b[i]a[i]==b[i]的可以作为山丘的两端，高度低的不能穿过他。
ACACAC代码：

#include
#include
#include
#include
using namespace std;
const int length = 2e5 + 5;
int a[length];
int b[length];
map mp;
int main(void)
{int t;scanf_s("%d", &t);for (int i = 0; i < t; i++){mp.clear();int n;scanf_s("%d", &n);for (int i = 0; i < n; i++){scanf_s("%d", &a[i]);}for (int i = 0; i < n; i++){scanf_s("%d", &b[i]);}int m;scanf_s("%d", &m);for (int i = 0; i < m; i++){int a;scanf_s("%d", &a);mp[a]++;}int flag = 1;stack s;for (int i = 0; i < n; i++){if (a[i] < b[i]){flag = 0;break;}while (!s.empty() && s.top() < b[i])s.pop();if ((s.empty() || s.top() > b[i])&&a[i]!=b[i]){s.push(b[i]);if (mp[b[i]] == 0){flag = 0;break;}mp[b[i]]--;}}if (flag == 0){printf("NO\n");}elseprintf("YES\n");}
}

还有就是这个题的数值太大了，本来想用离散化的，但是如果能用mapmapmap的话直接用mapmapmap吧，nnn是够的。

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：关于浮点数使用的两个注意事项(C/C++)

下一篇：【数据结构与算法学习8】二叉查找树的基本介绍与添加数据的过程

我用递归写单调栈(?)

相关内容

热门资讯