T5 合理的价格 题解

常规
,
1

T5 合理的价格 题解

\Huge{题目传送门}

思路

这题只需要先排序，然后再输入 t 个询问
然后在 n 个数里面找到比 p\cdot m 小的最大的价格
然后进行抹零和判断是不是 888 即可

这题如果纯模拟， O(n\cdot t) 会挂，所以我们需要使用二分来优化时间至 O(t\cdot \log n)
在 C++ 的 SLT 库里面有一个 upper_bound 函数
它可以在有序容器中查找第一个大于给定值的元素的位置（地址）
由于是地址，所以如果是在数组 a[] 里面查找的结果要减去数组名字 a
（如果你数组下标从一开始使用，那么就减去 a+1 ）
例如在 a[] 数组（大小为 n ）里查找第一个大于 3 的元素的位置就用 upper_bound(a,a+n,3)

然后只需要判断是否抹零和摆烂再输出即可 AC

code

#include<bits/stdc++.h>
using namespace std;
int t,k,n,p,m,a[100009];
int main(){
  freopen("price.in","r",stdin);
  freopen("price.out","w",stdout);
  //输入
  //sort
  for(int x=1;x<=t;x++){
    cin>>p>>m>>k;
   //二分
   //判断抹零（先判断抹零，再判断摆烂）
   if(价格<=a[1]||价格>=a[n])
    cout<< /*输出答案*/ <<endl;
  }
  return 0;
}
1 个赞