首页 > 其他分享 >CF706B 1100

CF706B 1100

时间:2023-02-16 16:11:06浏览次数:63  
标签:CF706B 正整数 int 商铺 num 1100 now id

题意

瓦西里喜欢喝"Beecola"饮料。 卖这种饮料的商铺有x家。每家的价格是x[i]元。 现在瓦西里 要买这种饮料n次,每次他最多能花n[i]元, 求他每次能在几个商铺买到至少一瓶饮料。
简短版:给出一个长度为x的数组,有n次询问, 输出 第n次询问的数大于等于几个x数组里的元素。
输入:第一行一个正整数x,表示商铺的数量。
第二行x个正整数,x[i],表示每家商铺中饮料的价格
第三行一个正整数n,表示询问的次数。
之后n行,每行一个正整数n[i],表示最多能花多少钱
输出:n行,每行一个正整数,表示每次能去几家商铺买到饮料

解析

二分模板题,但题意变了一下。
也可以离线处理,排序循环,如果询问递增就可以根据利用上次的结果,可以利用结构体排序

代码

//二分
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N],n,q;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	scanf("%d",&q);
	while(q--){
		int m;
		scanf("%d",&m);
		int pos = upper_bound(a+1,a+1+n,m) - a;
		printf("%d\n",pos-1);
	}

	return 0;
}
//思维 结构体排序
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,a[100001],now=1,ans[100001];
struct node{//由于输出需要按照原来的顺序输出,所以这里使用了结构体
	int num;//排序后第i次查询的内容
	int id;//排序前q[i]的下标
}q[100001];
bool cmp(node a,node b){
	return a.num<b.num;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>q[i].num;
		q[i].id=i;
	}
	sort(a+1,a+n+1);
	sort(q+1,q+m+1,cmp);
	for(int i=1;i<=m;i++){
		if(q[i].num>=a[n]){
			ans[q[i].id]=n;
			continue;
		}
		while(q[i].num>=a[now]){
			now++;
		}
		ans[q[i].id]=now-1;
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}

标签:CF706B,正整数,int,商铺,num,1100,now,id
From: https://www.cnblogs.com/dtdbm/p/17127127.html

相关文章

  • lg G3更新提示Err:0x1111004
    ​​G3更新提示Err:0x1111004​​一定要用最新的手机驱动程序上官网下载最新的支持工具LGMobileSupportTool,然后通过支持工具更新驱动,完成了连上手机选......
  • CF331C1 1100 *
    题意解析一开始以为是动态规划专题,想复杂了。其实就是模拟,每次挑最大的减。代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=......
  • CF363B 1100
    题意解析前缀和水题,就是在所有长度为k的区间里找个最小的。代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=2e5+10,M=......
  • CF368B 1100
    题意解析考察前缀知识。做的时候我好蠢,一直在想怎么前缀,大范围减小范围,怎么消除不同数字是否重复出现的影响。后来发现是自己蠢了,不就是求个后缀么。代码#include<bi......
  • CF313B 1100 *
    题意解析前缀和思想。f[i]用来代表到第i+1位有多少个满足s[k]==s[k+1]所以题目求从l~r,即求f[r-1]-f[l-1]代码#include<bits/stdc++.h>usingnamespacestd;ty......
  • DCDC直流隔离升压12V24V48V转600V800V1100V2500V3000V高压稳压输出电源模块
    特点●效率高达 80%●2*2英寸标准封装●单双电压输出●价格低●大于600V高压,稳压输出●工作温度:-40℃~+85℃●阻燃封装,满足UL94-V0要求●温度特性好●可直接......
  • 110004 求AB距离方位角已知点A点B坐标
    <?phpheader('Content-Type:text/html;charset=utf-8');define('ROOT',$_SERVER['DOCUMENT_ROOT']);includeROOT.'/assets/php/head.php';$tit='求AB距离方位角......
  • 110003 求点B坐标已知点A坐标AB距离方位角
    <?phpheader('Content-Type:text/html;charset=utf-8');define('ROOT',$_SERVER['DOCUMENT_ROOT']);includeROOT.'/assets/php/head.php';$tit='求点B坐标已知......
  • 110002 求最短距离和ABDE四角已知两点坐标
    <?phpheader('Content-Type:text/html;charset=utf-8');define('ROOT',$_SERVER['DOCUMENT_ROOT']);includeROOT.'/assets/php/head.php';$tit='求最短距离和AB......
  • 浪潮超融合inMerge1100刷新VMmark基准测试性能纪录
    近日,VMmark发布了最新的性能测试结果,浪潮信息inMerge1100超融合产品以25.74分的成绩,刷新了vSAN架构(Intel双路平台)的虚拟化性能测试记录。自2006年云计算概念问世以来,从服务......