好几位同学要的美团3.19笔试第一题,这是我的答案。
import java.util.ArrayList;
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
//原价前缀和
long[] priceSum=new long[n];
//折扣价前缀和
long[] discountSum=new long[n];
//原价前缀和赋值
for(int i=0;i<n;i++){
if(i==0){
priceSum[0]=scanner.nextInt();
}
else{
priceSum[i]=priceSum[i-1]+scanner.nextInt();
}
}
//折扣价前缀和赋值
for(int i=0;i<n;i++){
if(i==0){
discountSum[0]=scanner.nextInt();
}
else{
discountSum[i]=discountSum[i-1]+scanner.nextInt();
}
}
//满减种类个数
int manjianCount=scanner.nextInt();
//MyEntry类的定义看下面
ArrayList<MyEntry> myEntries=new ArrayList<>();
//这个数组的定义(主要是方便下面使用):例如满10减2,这个数组就会把10加入进来;再例如满15减5,这个数组就会把5加入进来;
int[] as=new int[manjianCount];
//给每个MyEntry的a赋值,并将其加入到列表中.
for(int i=0;i<manjianCount;i++){
MyEntry myEntry=new MyEntry();
myEntry.a=scanner.nextInt();
//给将a加入到as数组中,由于题目中满减的那个数目是从小到大的,所以as本身就是有序的.
as[i]=myEntry.a;
myEntries.add(myEntry);
}
//给每个MyEntry的b赋值
for(int i=0;i<manjianCount;i++){
myEntries.get(i).b=scanner.nextInt();
}
//用来记录结果
char[] res=new char[n];
for(int i=0;i<n;i++){
//在as这个数组中二分查找第一个小于等于priceSum[i]的值的索引
int index=BinarySearch.getIndexByBinarySearch(as,priceSum[i],0,manjianCount-1,false);
//这个索引可能找不到,例如as这个数组中的所有元素都大于priceSum[i],那么就不存在我们想找的索引.
if(index>=0){
//使用满减的话应该付的钱数
long manjianYuan=priceSum[i]-myEntries.get(index).b;
//使用折扣的话应该付的钱数
long discountYuan=discountSum[i];
long difference=manjianYuan-discountYuan;
//如果满减大于折扣,那就选折扣.
if(difference>0){
res[i]='Z';
}
else{
//如果满减小于折扣,那就选满减.
if(difference<0){
res[i]='M';
}
//等于就都可以
else{
res[i]='B';
}
}
}
//当索引找不到的时候说明没有可以使用的满减
else{
//比较原价和折扣价,要是相等的话表示折扣也用不了,那么这个时候可以认为满减和折扣是一样的.
if(priceSum[i]==discountSum[i]){
res[i]='B';
}
//要是不相等的话表示折扣肯定小于原价,那么这个时候折扣就是最好的,因为满减根本用不了.
else{
res[i]='Z';
}
}
}
//打印结果
for(int i=0;i<n;i++){
System.out.print(res[i]);
}
}
}
//这里面的a,b表示满a元减b元,例如满10减2,a就是10,b就是2.
class MyEntry{
public int a;
public int b;
}
class BinarySearch{
/**
*
* @param nums 要查找的数组
* @param target 要查找的数字
* @param left 数组的左边界位置(包含)
* @param right 数组的右边界位置(包含)
* @param isBigger 如果是true表示要查大于等于target的第一个元素,否则表示要查小于等于target的第一个元素.
* @return 找到的索引
*/
public static int getIndexByBinarySearch(int nums[],long target,int left,int right,boolean isBigger){
int mid=-1;
while(left<=right){
mid=(left+right)/2;
if(nums[mid]==target){
return mid;
}
else{
if(nums[mid]>target){
right=mid-1;
}
else{
left=mid+1;
}
}
}
//第一个比target小的
if(nums[mid]<target){
if(isBigger){
return mid+1;
}
return mid;
}
//第一个比target大的
else{
if(!isBigger){
return mid-1;
}
return mid;
}
}
}
#笔试题目##美团#