蓝桥杯第三天：2023蓝桥杯省赛 第 1 题

1、总价格要开 long 数据类型

2、直接贪心就行（优先找当前价格最贵的两个，然后再找当前能赠的价格最高的），找赠品的时候记得用二分（不然超时）

3、贪心不总是能找到最优解，但不能找最优解的情况不在测试用例里面 ，例如示例 6 12 23 25 25 50 50 输出 160 结果 150

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.util.Arrays;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner (System.in);
		int a[][] =new int[500005][2];
		int a1[] = new int[500005];
		int n = scan.nextInt();
		for(int i =0;i<n;i++)
			a1[i] = scan.nextInt();
		Arrays.sort(a1,0,n);
		for(int i = 0;i<n;i++) {
			a[n-1-i][0] = a1[i];
		}
		for(int i = 0;i<n;i++) {
			//System.out.print(a[i][0]+" ");
		}
		System.out.println();
		int count  = 0;
		long sum = 0;
		int m = 0;//最小的
		int aa = 0,bb=0;
		for(int i = 0;i<n;i++) {
			if(a[i][1]==1)
				continue;
		else if(aa==0) {
			aa =  a[i][0];
			a[i][1] = 1;
			sum += a[i][0];
			 //System.out.print(a[i][0]+" ");
			count++;
		}
		else if(bb==0&&aa!=0) {
			bb = a[i][0];
			a[i][1] = 1;
			sum += a[i][0];
			//System.out.print(a[i][0]+" ");
			count++;
			if(bb>aa)
				m = aa;
			else 
				m = bb;
		int r = n-1;
		int l = 0;//l这边是数字大的一边
		int mid = 0;
		while(l<=r) {
			 mid = (r+l)/2;
			if(a[mid][0]>(m/2))
				l = mid+1;
			else          
				r =mid-1;
		}
     if(a[l][1]==1) {
		while(a[l][1]==1&&l<n) {//必须要满足l<n，多加一个条件没坏处
		l++;//往小的找
		if(l<n&&a[l][1]==0&&l<n) {
			count++;
			a[l][1]=1;
			//System.out.print(a[l][0]+" ");
			break;
		}
		}
		}
     else if(a[l][1]==0&&a[l][0]<=m/2&&l<n){//必须要满足l<n，多加一个条件没坏处
    	 count++;
    	 a[l][1]=1;
    	 //System.out.print(a[l][0]+" ");
     }
				aa = 0;//复原
				bb = 0;
		}
		if(count==n)
			break;
		}
		System.out.println(sum);
	}
}//  8 4    2     7  5  1      1