做题小结1.23-1.31

https://codeforces.com/contest/1904/problem/B


这题目意思有点逆天 意思是说你可以设置你的初试分数为ai 然后大鱼吃小鱼 输出你设置为ai时吃到的最多
鱼数量 每个i都要输出

然后这是一个双指针的题目 也是一个二分的题目 考察基本功
我个人认为我现阶段就是基础不牢 所以对于这种橙题 我是很喜欢补的很透彻的 橙怎么了
场上卡你的还管什么颜色
先介绍双指针写法
结构体排序就不说了
很显然还是经典写法 卡住一边让r跑的写法 这个一边就是指我们for循环卡住i

for (int i = 1; i <= n; i++) {
		if (r>i) {
			ans[a[i].index] = r - 1;
			continue;
		}
		if(r!=i)
		tot += a[i].num;
		r=i;
		while (tot >= a[r + 1].num&&r<n) {
			tot += a[r + 1].num;
			r++;
		}
		ans[a[i].index] = r -1;		
	}

二分怎么写
这题双指针好写 但是二分不好写
我们先思考下 我们对于一个数需要清楚他吃了多少鱼（以他目前实力都能吃的）
然后吃完了后我们有一个前缀和 然后我们再看 这个前缀和他能延申到哪里呢？
很明显 我们可以预处理 当前缀和小于某个i时候是可以预处理的

我觉得可以这样预处理

来源链接：https://www.cnblogs.com/LteShuai/p/18804587