姜一墨
(Time Limit Exceeded)
1
2. 合理的价格
题目ID：15834必做题文件操作100分
最新提交：
Time Limit Exceeded
0 分
历史最高：
Wrong Answer
65 分
时间限制: 1000ms
空间限制: 524288kB
输入文件名: price.in
输出文件名: price.out
题目描述
财务部长鱼大大入职了海洋公司快5年了，这天老板鹏大大找到了他。
鹏大大：“小鱼呀，这几年我们几个竞争对手你都调查清楚了嘛？”
鱼大大：“老板，调查清楚了，这份表单是全部竞争对手的XY商品售价！”
鹏大大：“好！非常好！接下来我们也要推出XY商品了，小鱼呀，我要你定个合理的售价。记得我们的XY商品售价不能是同行里最高的，不然我们引了众怒，枪打出头鸟呢！也不能最低，会被怀疑掺假货的！emmmmmm，先定价和某个竞争对手的售价一样吧，就别高于我们成本的m倍，找个最高的售价作为我们XY商品的定价吧。”
鱼大大：“m倍？？？”
鹏大大：“你个笨蛋，m倍很多嘛？卖便宜了，我拿啥赚钱，高了m倍，别人说我吃相难看不买了怎么办。就这样吧，这样才能赚钱，懂了没有，这还要我教你的？？？”
鱼大大：“懂了懂了老板，肯定完成任务！还有别的要求嘛？”
鹏大大：“别着急呀，定价又不是售价，定价确定了之后，先看看有多少家售价比我们定价低的，要是有比k个或更多的竞争对手售价比我定价低，那我就...就在那定价上减一点凑个整作为最终售价吧，我少赚一些，到时候还能说给消费者抹零了嘿嘿嘿，否则的话，那就定这个售价了，该赚的还是要赚嘿嘿嘿。”
鱼大大：“？？？？？？”
鹏大大：“不行？？”
鱼大大：“保证完成任务！”
鹏大大：“你也别自己想了，你不手下还有一群聪明伶俐的学生嘛，让他们一起想！”
鱼大大：“好嘞！！”
现在，这个任务被分配到了你的手上，请你根据对话帮鱼大大一起解决这个问题，确定XY商品的最终售价，为了确保不会再被老板刁难，需要准备多组方案哦。
输入格式
所有输入数据从price.in文件中读取。
第一行1个整数n，表示为竞争对手的商品数量
第二行n个整数，分别为竞争对手的商品售价
第三行1个整数t，表示鱼大大要设计的方案总数
接下来t行，每行3个整数p,m,k表示鱼大大一组方案中的XY商品的成本，倍数m和竞争对手售价低于定价的数量
输出格式
所有输出数据输出到price.out文件
t行，每行一个整数表示合理的最大售价。（若找不到合理售价，鱼大大则摆烂直接输出888）
样例
Input 1
5
10 15 21 23 50
3
10 3 4
10 3 3
10 7 5
Output 1
23
20
888
样例解释
有5家竞争对手的XY商品售价分别为10 15 21 23 50
第一组询问10 3 4，表示成品10元，需要在不高于3倍成本（30元）的售价中找到最大一个，定价为23，此时，低于此定价的商家只有3个，故售价就为23。
第二组询问10 3 3，表示成品10元，需要在不高于3倍成本（30元）的售价中找到最大一个，定价为23，此时，低于此定价的商家有3个，故抹零，售价为20。
第二组询问10 7 5，表示成品10元，需要在不高于7倍成本（70元）的售价中找到最大一个，定价为50，此时，低于此定价的商家有4个，故售价就为50，但是因为售价不能为所有商家中最高，输出888。
#include<bits/stdc++.h>
using namespace std;
int n,a[100005],t,MAX=0,MIN=10005;
int main()
{
// freopen("price.in","r",stdin);
// freopen("price.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
MIN=min(MIN,a[i]);
MAX=max(MAX,a[i]);
}
sort(a+1,a+n+1);
cin>>t;
while(t--)
{
int p,m,k,mx=0,x=0;
scanf("%d %d %d",&p,&m,&k);
int h=p*m;
int l=0,r=n+1,mid;
while(l<r)
{
mid=(l+r)/2;
if(a[mid]<=h and a[mid]>mx)
{
l=mid;
mx=a[l];
}
else
r=mid;
}
int ll=0,rr=n+1,midd;
while(ll<rr)
{
midd=(ll+rr)/2;
if(a[midd]>mx)
ll=midd;
else
rr=midd;
}
// int j=l;
// while(a[j]>=mx)
// j--;
x=ll+1;
if(x>=k)
{
int h=mx%10;
mx-=h;
}
if(mx==MAX or mx==MIN or mx==0)
printf("888\n");
else
cout<<mx<<endl;
}
return 0;
}