虚拟主机网站源码,做网站公司大型,网络推广营销平台系统,营销方案的几个要素试题
糖糖别胡说#xff0c;我真的不是签到题目 时间限制#xff1a;C/C 2秒#xff0c;其他语言4秒 空间限制#xff1a;C/C 131072K#xff0c; 其他语言262144K 64bit IO Format:%lld 题目描述 从前#xff0c;有n只萌萌的糖糖#xff0c;他们分成了两组一起玩游戏。…试题
糖糖别胡说我真的不是签到题目 时间限制C/C 2秒其他语言4秒 空间限制C/C 131072K 其他语言262144K 64bit IO Format:%lld 题目描述 从前有n只萌萌的糖糖他们分成了两组一起玩游戏。他们会排成一排第i只糖糖会随机得到一个能力值bi。从第i秒的时候第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。 为了使游戏更加有趣糖糖的爸爸娇姐会发功m次第i次发功的时间为ci则在第ci秒结束后b1,b2,…,bci都会增加1. 现在娇姐想知道在第n秒后会有多少只糖糖存活下来。 输入描述: 第一行只有一个整数TT6表示测试数据的组数。 第二行有两个整数n,m。表示糖糖的个数以及娇姐发功的次数。1n50000,1bi1000000 第三行到n2行,每行有两个整数ai,bi,表示第i只糖糖属于那一组以及他的能力值。0ai1,1bi1000000 第n3行到第nm2行每行有一个整数ci表示GTW第i次发功的时间.(1cin) 输出描述: 总共T行第i行表示第i组数据中糖糖存活的个数。 示例1 输入
1 4 3 0 3 1 2 0 3 1 1 1 3 4输出
3题解
我们先想想一个糖糖能活下来需要什么条件 就是在它后面不存在一个比他的大的且不在一个组 两个要求不能比他大且不在一组 这样我们其实就可以从后往前扫描因为这样扫描过的不会再被消灭我们就不用再管了来维护当前位置往后每一组糖糖的最大值然后比较如果比这个位置大这个位置的糖糖不就被消灭了
还有个发功问题头大 发功后并不是都1而是前ci个人!,前ci个人之间的相对大小并没发生改变所以不影响第ci个糖糖在第ci秒消灭他前面的糖糖。 而第ci之后的并没有1那咋办我们可以用每个人最后的能力值来判断到底能不能存活 我们先求出每个糖糖最后的能力值倒着判断每个糖糖是否能存活用前缀和优化
具体看代码
#includebits/stdc.h
#define forr(n) for(int i1;in;i)
typedef long long ll;
using namespace std;
const ll maxn1e52;
ll t;
ll n,m;
ll s[maxn];
ll a[maxn];
ll b[maxn];
ll pre[maxn];
ll sum,maxx,maxx1;
int main(){cint;while(t--){cinnm;forr(n){cina[i]b[i]; }forr(m){ll w;cinw;s[w];}for(int in;i1;i--) pre[i]pre[i-1]s[i];for(int in;i1;i--){b[i]pre[i];if(!a[i]){if(b[i]maxx1) maxx1b[i];//更新0队伍的最大值 if(b[i]maxx) sum;}else{if(b[i]maxx) maxxb[i];//更新1队伍最大值 if(b[i]maxx1) sum; }}coutn-sum;}return 0;
}/*
1
4 3
0 3
1 2
0 3
1 1
1
3
4
*/
