题意
瓦西里喜欢喝"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