当前位置：首页 > news >正文

第七讲贪心

news 文章来源：https://blog.csdn.net/qq_52986400/article/details/129685018 2025/2/12 17:50:15

文章目录

- 股票买卖 II
- 货仓选址（贪心:排序+中位数）
- 糖果传递（❗·贪心：中位数）
- 雷达设备（贪心+排序）
- 付账问题（平均值+排序❓）
- 乘积最大（排序/双指针）
- 后缀表达式（👍绝对值/分类讨论/贪心）

股票买卖 II

在这里插入图片描述
思路：只要对于今天来说明天的价格比今天高，我们就买，明天卖了肯定会获利。

public class Main{static Scanner sc = new Scanner(System.in);static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e5 + 10);static int[] a = new int[N];static long ans = 0;public static void main(String[] args) throws Exception{int n = sc.nextInt();for(int i = 1; i <= n; i++) {a[i] = sc.nextInt();}for(int i = 2; i <= n; i++) {if(a[i] > a[i - 1]) {ans += (a[i] - a[i - 1]);}}System.out.println(ans);}
}

货仓选址（贪心:排序+中位数）

在这里插入图片描述
选中位数对两边来说都比较优


public class Main{static Scanner sc = new Scanner(System.in);static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e5 + 10);static int[] a = new int[N];static long ans = 0;public static void main(String[] args) throws Exception{int n = sc.nextInt();for(int i = 1; i <= n; i++) {a[i] = sc.nextInt();}Arrays.sort(a,1, 1 + n);int mid = (n + 1)/2;for(int i = 1; i <= n; i++) {ans = ans + Math.abs(a[i] - a[mid]);}System.out.println(ans);}
}

糖果传递（❗·贪心：中位数）

本人还不是太明白

雷达设备（贪心+排序）

在这里插入图片描述
这道题也不太会，太菜了，😢
看的别人的题解，很妙题解

首先我们需要将小岛的坐标转换为区间，x只有在[x1,x2]才可以被搜到。
转换为以后就变成了区间覆盖问题，但是我们需要对区间从小到达（右端点）从小到大排序，我们只需要哦使用最近的雷达去判断是否可以，如果不可以就需要在加一个。

import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;public class Main{static Scanner sc = new Scanner(System.in);static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e4 + 10);static node[] a = new node[N];static int ans = 0;static int n = 0,d = 0;static boolean[] vis = new boolean[N];public static void main(String[] args) throws Exception{n = sc.nextInt();d = sc.nextInt();for(int i = 1; i <= n; i++) {int x,y;x = sc.nextInt();y = sc.nextInt();y = Math.abs(y);if(y > d) {System.out.println(-1);return;}a[i] = new node();a[i].l = x - Math.sqrt(d*d-y*y);a[i].r = x + Math.sqrt(d*d-y*y);}Arrays.sort(a,1,1 + n,new cmp());
//		for(int i = 1; i <= n; i++) {
//			System.out.println(a[i].r);
//		}for(int i = 1;i <= n; i++) {if(!vis[i]) {ans++;vis[i] = true;for(int j = i + 1; j <= n; j++) {if(a[j].l <= a[i].r) {vis[j] = true;}}}}System.out.println(ans);}
}
class node{double l,r;
}
class cmp implements Comparator<node>{public int compare(node o1, node o2) {if(o1.r < o2.r) {return -1;}else {return 1;}}}

付账问题（平均值+排序❓）

在这里插入图片描述

思路：显然是所有人付的钱越接近平均数标准差越小，我们让所有人的数据尽可能接近标准差，首先算出平均值，然后将其进行排序，低于平均值的人把所有钱都拿出来，其余的由其他人平摊（需要注意精度问题，竟然还要用long double）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>using namespace std;const int N = 500010;int n;
int a[N];int main()
{long double s;cin >> n >> s;for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);sort(a, a + n);long double res = 0, avg = s / n;for (int i = 0; i < n; i ++ ){double cur = s / (n - i);//当前需要交多少钱if (a[i] < cur) cur = a[i];//如果当前的钱不够，那么就全部交res += (cur - avg) * (cur - avg); //把平方加到答案里面s -= cur;//剩下需要交的钱就减少了cur}printf("%.4Lf\n", sqrt(res / n));return 0;
}

乘积最大（排序/双指针）

在这里插入图片描述

在这里插入图片描述
思路：对于k是奇数且k<n的情况，我们需要特殊处理一下，转换为普遍情况，我们取一个最大的数，此时k就转换为偶数，我们可以使用双指针算法，首先对所有数进行排序，很显然负数绝对值大的在左边，偶数绝对值大的在右边，如果必须选一个正的一个负的话，显然是选的负数绝对值较小的与正数数值较小的，加个负号，显然是比较小的。

public class Main{static Scanner sc = new Scanner(System.in);static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = 100010;static int ans = 0;static int n = 0,k = 0;static int[]a = new int[N];static int mod = 1000000009;public static void main(String[] args) throws Exception{n = sc.nextInt();k = sc.nextInt();for(int i = 1; i <= n; i++) {a[i] = sc.nextInt();}Arrays.sort(a,1,1 +n);long res = 1;//初始化乘积int l = 1, r = n;int sign = 1;//标记符号位if(k % 2 == 1) {res = a[r--];//选取最大的一个数if(res < 0) {sign = -1;}k--;}while(k > 0) {long x = (long)a[l] * a[l+1];long y = (long)a[r] * a[r-1];if(x * sign > y * sign) {res = ((res % mod) * (x % mod));//不太懂为啥l += 2;}else {res = ((y % mod) * (res % mod));r -= 2;}k-=2;}System.out.println(res%mod);}//	static int md(int x) {
//		if(x > 0) {
//			return x%mod;
//		}else {
//			
//		}
//	}}


public class Main{static Scanner sc = new Scanner(System.in);static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = 100010;static int ans = 0;static int n = 0,k = 0;static int[]a = new int[N];static int mod = 1000000009;public static void main(String[] args) throws Exception{n = sc.nextInt();k = sc.nextInt();for(int i = 1; i <= n; i++) {a[i] = sc.nextInt();}Arrays.sort(a,1,1 +n);long res = 1;//初始化乘积int l = 1, r = n;int sign = 1;//标记符号位if(k % 2 == 1) {res = a[r--];//选取最大的一个数if(res < 0) {sign = -1;}k--;}while(k > 0) {long x = (long)a[l] * a[l+1];long y = (long)a[r] * a[r-1];if(x * sign > y * sign) {res = (md(x) * md(res));//不太懂为啥l += 2;}else {res = (md(y) * md(res));r -= 2;}k-=2;}System.out.println(md(res));}static long md(long x) {if(x > 0) {return x % mod;}else {return 0-((0-x)%(long)1000000009);}}}

是否判断正负都是可以的，不太懂

后缀表达式（👍绝对值/分类讨论/贪心）