迷你滨

用户名：uq_20629230267

访问量：9282

签　名：

等　　级
排　　名	2135
经　　验	2437
参赛次数	0
文章发表	13
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2023年第十四届省赛真题-网络稳定性(最大生成树+LCA)
浏览：1425

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

蓝桥杯2023年第十四届省赛JavaB -买二赠一（贪心＋二分）

　　作者: 迷你滨　　　　发表时间：2023-04-14 21:09:41 浏览：575　|　评论：1　

原题链接：蓝桥杯2023年第十四届省赛真题-买二赠一

### 蓝桥杯2023年第十四届省赛JavaB -买二赠一 （贪心＋二分）
先排序，每次贪心地选最大的没买/赠的物品a,b，然后选剩下的的最大不超过min(a/2,b/2)的物品，赠送的物品的价值显然不会增大，故可以二分。
```Java
import java.util.*;
import java.io.*;
public class Main {
	static int n,m,mod=(int)1e9+7,maxn=500010;
	static long ans=0,INF=(long)1e18;
	static Scanner sc = new Scanner (System.in);
	static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	static StreamTokenizer st = new StreamTokenizer(bf);
	static PrintWriter pw = new PrintWriter(System.out);
	
	public static void main(String[]args) throws IOException{
		int T = 1;
		//T = I();
		while(T-->0) solve();
		pw.flush();
	}
	
	static int I() throws IOException{
		st.nextToken();
		return (int)st.nval;
	}
	
	static int a[] = new int [maxn];
	static boolean f[] = new boolean [maxn];
	
	static int find(int x) {
		int l=1,r=n;
		int res =0;
		while(l<=r) {
			int mid = (l+r)/2;
			if(f[mid]) { //先前赠送过，跳到左边
				r=mid-1;continue;
			}
			if(a[mid] <= x) {
				res = Math.max(res, mid);
				l = mid+1;
			}
			else r = mid-1; 
		}
		return res;
	}
	
	static void solve() throws IOException{
		n = I();
		for(int i=1 ;i<=n;i++) a[i]  =I();
		Arrays.sort(a,1,n+1);
		int t = 0;
		for(int i=n;i>=1;i--) {
			if(f[i]) continue;//赠送过，跳过
			ans += a[i];
			t++;
			if(t == 2) {
				t=0;
				int id = find(a[i]/2);
				if(id>0) f[id]=true;
			}
		}
		pw.println(ans);
	}
	
}

```

0.0分

9 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

李白

二分写的很好

2023-04-29 17:14:41

迷你滨

TA的其他文章

你可能喜欢

C二级辅导-等差数列（C++代码）

Lucky Word （C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

陶陶摘苹果（C语言代码）

C二级辅导-计负均正（C语言代码）

蓝桥杯2023年第十四届省赛JavaB -买二赠一（贪心＋二分）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

1011题解

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

矩形面积交（C语言代码）

C二级辅导-等差数列（C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

简单的a+b （C语言代码）

汽水瓶（C语言代码）

迷你滨

TA的其他文章

你可能喜欢

C二级辅导-等差数列 （C++代码）

Lucky Word （C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

陶陶摘苹果 （C语言代码）

C二级辅导-计负均正 （C语言代码）

蓝桥杯2023年第十四届省赛JavaB -买二赠一 （贪心＋二分）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

1011题解

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

矩形面积交 （C语言代码）

C二级辅导-等差数列 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

简单的a+b （C语言代码）

汽水瓶 （C语言代码）

C二级辅导-等差数列（C++代码）

陶陶摘苹果（C语言代码）

C二级辅导-计负均正（C语言代码）

蓝桥杯2023年第十四届省赛JavaB -买二赠一（贪心＋二分）

　　评论区

矩形面积交（C语言代码）

C二级辅导-等差数列（C语言代码）

汽水瓶（C语言代码）