首页 > 其他分享 >贪心杂题

贪心杂题

时间：2022-09-26 20:13:14浏览次数：78  
标签：int Luogu re freopen tie 贪心 杂题 define

\(Preface\)

最近咋老考贪心嘞？我的数据结构呢？

贪心这玩意确实重要。但是我蒟蒻，老做不出来，而且经常写挂某些需要用到一些小技巧的题。。。

具体地，刷贪心题既是刷思维也是刷能力。

其实就是刷水题来了

\(\mathfrak{Luogu\ P1007}\ 独木桥\)

还是第一篇题解说的那样，从高空看两个人相遇之后回头继续走，看起来就像两个人互相穿过了一样。

然而确实是这样的。两个人相遇后回头，就等同于各走各的继续走。

直接对于每一个人往左和往右走分别取min max就行了。

注意几个人是同时在走的，所以在原来分别取min max的同时，对所有人走出去需要的时间取一个max即为答案。

$Luogu-P1007$ 
#include <iostream>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define re register int
#define char_phi signed
#define DMARK cerr << "###"
#define _ ' '
#define Endl cout << '\n'
#define Dl cerr << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
/*
	不知道贪心对不对
	mid：len>>1
	最优：
	<= mid：->左
	> mid： ->右
	最劣：
	<= mid
	谔 这好像不是很水的贪心?
	*(康题解)*
	超！
*/
int len, n, mnans, mxans;
inline void work(){
	cin >> len >> n;
	for (re i = 1, plc ; i <= n ; ++ i)
		{cin >> plc; mnans = MAX(mnans, MIN(plc, len-plc+1)), mxans = MAX(mxans, MAX(plc, len-plc+1));}
	cout << mnans << _ << mxans << '\n';
}
// #define IXINGMY
char_phi main(){
	#ifdef IXINGMY
		FBI_OPENTHEDOOR(a);
	#endif
	Fastio_setup();
	work();
	return GMY;
}

\(\mathfrak{Luogu\ P2240} 【深基12.例1】部分背包问题\)

按照性价比排序，选就行了。题目都提示的这么明显了。。。

分割完的金币重量价值比（也就是单位价格）不变。

$Luogu-P2240$ 
#include <iostream>
#include <algorithm>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define re register int
#define char_phi signed
#define DMARK cerr << "###"
#define _ ' '
#define Endl cout << '\n'
#define Dl cerr << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 105
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
struct node{
	int m, w; double cpr;
	friend bool operator < (node A, node B){return A.cpr > B.cpr;}
};
/*
	题干直接说做法了这
	性价比排个序就完事了
*/
int n, capacity;
double final_ans;
struct node a[N];
inline void work(){
	cin >> n >> capacity;
	for (re i = 1 ; i <= n ; ++ i)
		{cin >> a[i].m >> a[i].w; a[i].cpr = (double)a[i].w/a[i].m;}
	sort(a+1, a+n+1);
	for (re i = 1 ; i <= n ; ++ i){
		if (capacity - a[i].m < 0)
			{final_ans += capacity * a[i].cpr; capacity = 0; break;}
		else 
			final_ans += a[i].w, capacity -= a[i].m;
	}
	cout.setf(ios::fixed), cout.precision(2);
	cout << final_ans << '\n';
}
// #define IXINGMY
char_phi main(){
	#ifdef IXINGMY
		FBI_OPENTHEDOOR(a, a);
	#endif
	Fastio_setup();
	work();
	return GMY;
}

\(\mathfrak{Luogu\ P1223}\ 排队接水\)

显然让接水时间短的先接。注意他问的是等待时间的平均值，不用算上本身接水的时间。

记得开long long

$Luogu-P1223$ 
#include <iostream>
#include <algorithm>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define re register int
#define char_phi signed
#define DMARK cerr << "###"
#define _ ' '
#define Endl cout << '\n'
#define Dl cerr << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 1005
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
struct Person{
	int ai, id;
	friend bool operator < (Person A, Person B){
		return A.ai < B.ai;
	}
};
/*
	直接按照ti sort一遍即可
*/
int n;
long long final_ans;
struct Person a[N];
inline void work(){
	cin >> n;
	for (re i = 1 ; i <= n ; ++ i)
		{cin >> a[i].ai; a[i].id = i;}
	
	sort(a+1, a+n+1);
	
	for (re i = 1, j = n-1 ; i <= n ; ++ i, -- j){
		final_ans += (long long)a[i].ai*j;
	}
	
	for (re i = 1 ; i <= n ; ++ i)
		cout << a[i].id << _;
	Endl;
	/*for (re i = 1 ; i <= n ; ++ i)
		cerr << a[i].ai << _;
	Dl;*/
	cout.setf(ios::fixed), cout.precision(2);
	cout << ((long double)final_ans/n) << '\n';
}
// #define IXINGMY
char_phi main(){
	#ifdef IXINGMY
		FBI_OPENTHEDOOR(a, a);
	#endif
	Fastio_setup();
	work();
	return GMY;
}

\(\mathfrak{Luogu\ P1803}\ 凌乱的yyy / 线段覆盖\)

考虑下面的情况：

|<------------------->|
|<----->|  |<---->|

显然选第二行的更优。

那么就有了较为朴素的 \(dp\) 转移想法，既 \(check\) 某一个区间是否能够被更多的区间所替代，相应地选择是否更新 \(dp\) 值。

其实是不需要 \(dp\) 的，直接 \(sort\) 右端点去选就行了

$Luogu-P1803$ 
#include <iostream>
#include <algorithm>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define re register int
#define char_phi signed
#define DMARK cerr << "###"
#define _ ' '
#define Endl cout << '\n'
#define Dl cerr << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 1000005
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
struct XD{
	int ai, bi;
	friend bool operator < (XD A, XD B){return A.bi < B.bi;}
};
/*
	直接题目映射做法是吧
	似乎是维护线段覆盖，使得连续的线段能够最长
	*(看题解)*
	没看懂
	问kirito
	好家伙直接一个反证法证出来了
	考虑这样的情况
	|<-------------->|
	|<-->| |<---->|
	显然选下面的更优
	所以直接求出来当前点的最优解，用此最优解去更新下一个最优解
	没错，dp
	但是不用dp就能实现，sort右端点就行了
*/
int n, final_ans;
struct XD a[N];
inline void work(){
	cin >> n;
	for (re i = 1 ; i <= n ; ++ i)
		cin >> a[i].ai >> a[i].bi;
	sort(a+1, a+n+1);
	int plc = a[1].bi;
	final_ans = 1;
	for (re i = 2 ; i <= n ; ++ i)
		if (a[i].ai >= plc)
			plc = a[i].bi, final_ans ++;
	cout << final_ans << '\n';
}
// #define IXINGMY
char_phi main(){
	#ifdef IXINGMY
		FBI_OPENTHEDOOR(a, a);
	#endif
	Fastio_setup();
	work();
	return GMY;
}

\(\mathfrak{Luogu\ P1090}\ [NOIP2004 提高组]\ 合并果子\ /\ [USACO06NOV]\ Fence\ Repair\ G\)

虎哥讲过。而且很简单吧。。远古时期的水题

直接贪心地先让最小的合并，用一个set维护最小值，然后合并之后再扔进set，最后set里元素就剩一个的时候break，期间统计答案即可。

$Luogu-P1090$ 
#include <iostream>
#include <set>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define re register int
#define char_phi signed
#define DMARK cerr << "###"
#define _ ' '
#define Endl cout << '\n'
#define Dl cerr << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
/*
	那显然是先合并最小的？
	用一个multiset维护就行了
*/
int n, final_ans;
multiset<int> s;
inline void work(){
	cin >> n;
	if (n == 0)
		return ;
	for (re i = 1, w ; i <= n ; ++ i)
		{cin >> w; s.insert(w);}
	while (s.begin() != prev(s.end())){
		int w1 = *s.begin(); s.erase(s.begin());
		int w2 = *s.begin(); s.erase(s.begin());
		final_ans += w1+w2;
		s.insert(w1+w2);
	}
	cout << final_ans << '\n';
}
// #define IXINGMY
char_phi main(){
	#ifdef IXINGMY
		FBI_OPENTHEDOOR(a, a);
	#endif
	Fastio_setup();
	work();
	return GMY;
}

标签：int,Luogu,re,freopen,tie,贪心,杂题,define
From： https://www.cnblogs.com/charphi/p/16731649.html

相关文章

  • CSP 2022 备战 贪心算法
    基本思路：1.建立数学模型来描述问题2.把求解的问题分成若干个子问题3.对每一子问题求解，得到子问题的局部最优解4.把子问题的局部最优解合并成一个解贪心的使用前提：局部......
  • ARC杂题
    实际上如果你觉得你切了两道题但是没拍的话那就真的会保龄。所以我挂了200。警钟长鸣。ARC125C使字典序最小的话，他给了\(k\)个我们需要扔掉最后一个不看，要不然可能不优......
  • CF1718D Permutation for Burenka【贪心】
    传送门显然，两个数列相似当且仅当它们的笛卡尔树结构相同。那么排列\(p\)给出了\(a\)所对应的笛卡尔树形态，据此我们容易求出树上每个空位上数的取值范围\([l_i,r_i]......
  • 9 月杂题选做
    觉得比较有意思的题，坑LuoguP6824「EZEC-4」可乐\(k\)是已知的，我们要确定一个\(x\)，不妨直接枚举这个\(x\)。显然\(x\leq2^{21}\)，然后涉及异或，考虑字典树。......
  • 道长的算法笔记：贪心算法经典模型
    (一)区间模型(1.1)区间合并(1.2)区间选点(1.3)区间覆盖(1.4)区间分组(二)贪心常用证明方法......
  • jz42连续字数的最大和(动态规划,贪心)
    publicclasssolution{ publicintmaxOfSubarray(int[]array){   int[]dp=newint[array.length];   dp[0]=array[0];   intmax=array[0]; ......
  • 使用贪心来解决的一些问题
    使用贪心来解决的一些问题作者：Grey原文地址：博客园：使用贪心来解决的一些问题CSDN：使用贪心来解决的一些问题贪心的使用方法分析业务根据业务逻辑找到不同的贪心策......
  • 【杂题合集】震惊！这种生活习惯可能致癌！99%的人都有......
    杂题合集标题党去死CF1714EAddModulo10题意概述：给出一个序列，可以给其中任意一个数加上当前它的个位数，问进行若干次操作后这个序列里的数能否全部相等。解析：思维......
  • 9月杂题选做
    上回说到：2022.8关于难度\(\color{gray}\bigstar\)可以秒杀的题。\(\color{green}\bigstar\)思考一会儿后可以秒的题。\(\color{blue}\bigstar\)需要较长时间思考的......
  • gk的树（贪心 dfs） 哈理工程序设计竞赛
    题目：​给你一棵树，每次操作你可以删去一条边，最少需要多少次操作使每个节点的度数都\(<=k\)分析：​我们可以想一想如何贪心，对于本题，最优的结果是让任意一个点连的边最多......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99