首页 > 其他分享 >Codeforces Round 856 (Div. 2)C

Codeforces Round 856 (Div. 2)C

时间:2023-05-06 13:23:26浏览次数:51  
标签:856 run int 最大值 Codeforces long Div

C. Scoring Subsequences

思路:我们想要找到满足的最大值的长度最长的的区间,因为单调不减,所以更大的数一定在最大值的里面包含,所以我们用两个指针维护这样一个满足当前i的最大值区间,当新来一个数,这时我们答案里面一定要包含这个数,我们看能否保持这个长度,能不能保持需要看j指针所指的数/区间长度和1的大小比较,如果大于1乘上去一定可以使结果增大,反之会使结果减小,那么这个数就不能要了。

#include <bits/stdc++.h>
 
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int a[N]; 
int ans = 0;
void run()
{	
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++ i)	scanf("%d", &a[i]);
	for(int i = 1, j = 1; i <= n; ++ i)
	{
		while(j <= i && a[j] / (i - j + 1) < 1)	++ j;
		cout << i - j + 1 << ' ';
	}
	cout << endl;
}
 
int main()
{
//	freopen("1.in", "r", stdin);
	int t;cin >> t;
	while(t --)	run();	
	return 0;  
}

标签:856,run,int,最大值,Codeforces,long,Div
From: https://www.cnblogs.com/cxy8/p/17376957.html

相关文章

  • Codeforces——870
    A.TrustNobody题目大意给你一个长度为\(n\)的数组\(a\),\(a\)中每个元素\(a_i\)表示当前人认为\(n\)个人中至少有\(a_i\)个人说谎,让你找出说谎的人的个数。思路:枚举说谎人数\(x\),遍历\(a\)数组,对于当前\(a_i\),如果有\(a_i\geqx\),那么显然第\(i\)个人在说谎,记录人数看是否等......
  • 外设驱动库开发笔记53:MAX31856热偶变送器驱动
      在我们的产品中经常有需要温度检测的地方,而热电偶温度检测电路是我们常用的。热电偶温度检测的方法很多,有时出于简单方便的考虑我们会选择热偶温度变送器来实现,这一篇我们就来讨论使用MAX31856热电偶温度变送器实现温度的检测。1、功能概述  MAX31856可以对任何类型热电偶的......
  • [CodeForces-143A]题解(C++)
    PartIPreface原题目(Luogu)原题目(CodeForces)PartIISketch设有一个\(2\times2\)的棋盘,上面可以填入\(1-9\)的数字。给出\(6\)个数字,为每行每列以及每个对角线上的数字之和,求相应的摆放方式,无解输出\(-1\)。PartIIIAnalysis观察此题数据规模,不难发现数据......
  • [CodeForces-1104A]题解(C++)
    PartIPreface原题目(Luogu)原题目(CodeForces)PartIISketch给定一个整数\(n\)。将\(n\)拆分成一个数列\(a_1,a_2,a_3,\dots,a_m\)。使得\(\sum\limits_{k=1}^{m}a_k=n\),每个\(a_i\in[0,9]\)且数列中不相同的数的数量尽量少。PartIIIAnalysis我们很容易......
  • [CodeForces-545A]题解(C++)
    PartIPreface原题目(Luogu)原题目(CodeForces)PartIISketch给定一个正整数\(n\),表示汽车数量。给定一个\(n\timesn\)阶矩阵\(A\),第\(i\)行\(j\)列上的数字表示\(i\)车与\(j\)车的对撞情况。\(\begin{aligned}\begin{cases}A_{i,j}=-1&i,j\text{车没......
  • [CodeForces-545A]题解(C++)
    PartIPreface原题目(Luogu)原题目(CodeForces)PartIISketch给定一个正整数\(n\),表示汽车数量。给定一个\(n\timesn\)阶矩阵\(A\),第\(i\)行\(j\)列上的数字表示\(i\)车与\(j\)车的对撞情况。\(\begin{aligned}\begin{cases}A_{i,j}=-1&i,j\text{车没......
  • Educational Codeforces Round 147 (Rated for Div. 2) (贪心)
    原题链接:https://codeforces.com/contest/1821/problem/D*题意:从1开始走,走的给定区间的值要k次。且shift按了要松开,代表走了一个区间除了往右的次数,还要多两次按shift的次数,求最小次数。*思路:1.先把不可能的情况列出来,就是给出的区间大小小于k时直接输出-12.我的思路是暴......
  • Codeforces Round 867 (Div. 3)
    A.TubeTubeFeed分析:从所有a[i]+i-1<=t的选择种取个max即可code:#include<bits/stdc++.h>usingnamespacestd;constintN=55;inta[N],b[N];intmain(){std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0); intt; cin>>t;......
  • Codeforces 908H - New Year and Boolean Bridges(FWT)
    一道挺有意思的题,并且感觉有点诈骗的成分在内(首先考虑分析三种字符的性质:显然任意两点\(i,j\)之间要么\(i\)可以到达\(j\),要么\(j\)可以到达\(i\),否则AOX三个一个都不能满足。如果两点间的状态是A,那么这两点必须在同一强连通分量内。如果两点间的状态是X,那么这......
  • 4.[1201D - Treasure Hunting](https://codeforces.com/problemset/problem/1201/D)
    4.1201D-TreasureHunting题目意思:在一个n*m的地图上面,左下角的坐标是(1,1),最开始你位于左下角,一秒钟你可以进行往左或者往右的操作,你只能在一些特殊的列上面进行往上移动的操作,你不可以往下移动。现在告诉你k个宝藏的坐标信息以及哪些列是允许往上的,问最后至少要几秒可以遍历k......