建设网站怎么判断是电脑还是手机号码,可以做点赞的网站,世界500强企业门槛,开发网站建设方案Problem - D - Codeforces
问题描述#xff1a;剪发#xff0c;将数组a减为数组b#xff0c;有m个剪刀#xff0c;每个剪刀只可以用一次且可以在任意区间内剪发#xff0c;将长度大于mi的减为mi。现在有m数组#xff0c;数组元素是第i个剪刀可以剪到mi#xff0c;问能否…Problem - D - Codeforces
问题描述剪发将数组a减为数组b有m个剪刀每个剪刀只可以用一次且可以在任意区间内剪发将长度大于mi的减为mi。现在有m数组数组元素是第i个剪刀可以剪到mi问能否将a减为b。
洛谷翻译 思路一定是先减最长的再减短的。在减的时候会将这个a数组渐渐减成多个数组再对这些数组进行这些操作判断给出的m数组是否满足可以进行这些操作。
如果是b[0]因为是第一个所以一定需要一个剪刀m b[0]。
到b[1]时有三种情况
b[1] b[0]因为接下来要减的少所以也要用一个剪刀m b[1]。b[1] b[0]相同上一个可以被覆盖不需要额外操作。b[1] b[0]这是由于b[1] b[0]前面大于b[1]的剪刀都不可以用。因为如果用了那么a[1]就会小于b[1]此时不满足条件。
发现此时具有单调栈性质通过从0到n-1进行遍历b数组先将栈中小于bi的出栈之后判断是否为空或者已经存在栈中sk.top() bi)如果为空或者bi不在栈中入栈表示一定需要这个
代码
void solve() {int n; cinn;vectorint a(n), b(n);for(auto t: a) cint;for(auto t: b) cint;bool ok true;for(int i 0; i n; i) if(a[i] b[i]) ok false;mapint,int mii;int m; cinm;for(int i 0; i m; i) {int t; cint;mii[t];}stackint sk;for(int i 0; i n; i) {while(sk.size() sk.top() b[i]) sk.pop();if(a[i] b[i]) continue;if(sk.empty() || sk.top() ! b[i]) {sk.push(b[i]);mii[b[i]]--;}}for(auto t: mii) {ok t.vs 0;}puts(ok ? YES : NO);
}
