贪心 学习笔记

贪心 学习笔记,第1张

简介

贪心的一种方法,那就是写一个 comparator 比较器。


便于在排序时使用。


一般来说,选择 2 2 2 个 index,列出一个数学关系式,判断是交换更优还是维持原样更好。


例题 1 1 1

P1080 [NOIP2012 提高组] 国王游戏

A A A 为当前状态的积。


i , j i,j i,j 为我们考虑的一对下标。


m a x ( A b i , a i A b j ) ⩽ m a x ( A b j , a j A b i ) max(\frac{A}{b_i},\frac{a_iA}{b_j})\leqslant max(\frac{A}{b_j},\frac{a_jA}{b_i}) max(biA,bjaiA)max(bjA,biajA)

( A b i ⩽ A b j o r A b i ⩽ a j A b i ) a n d ( a i A b j ⩽ A b j o r a i A b j ⩽ a j A b i ) (\frac{A}{b_i}\leqslant \frac{A}{b_j} or \frac{A}{b_i}\leqslant \frac{a_jA}{b_i}) and (\frac{a_iA}{b_j} \leqslant \frac{A}{b_j} or \frac{a_iA}{b_j}\leqslant \frac{a_jA}{b_i}) (biAbjAorbiAbiajA)and(bjaiAbjAorbjaiAbiajA)

( b j ⩽ b i o r 1 ⩽ a j ) a n d ( a i ⩽ 1 o r a i b i ⩽ a j b j ) (b_j\leqslant b_i or 1\leqslant a_j) and (a_i\leqslant 1 or a_ib_i\leqslant a_jb_j) (bjbior1aj)and(ai1oraibiajbj)

这个式子中, 1 ⩽ a j 1\leqslant a_j 1aj 是必然的,所以上式左部分恒为 1 1 1


a i ⩽ 1 a_i\leqslant 1 ai1 是永远不可能的。


因此,这个式子是否为 1 1 1 取决于 a i b i ⩽ a j b j a_ib_i\leqslant a_jb_j aibiajbj


这样,如果不需要交换,满足的条件应为 a i b i ⩽ a j b j a_ib_i\leqslant a_jb_j aibiajbj


也就是这一段。


// comparator
bool operator <(node a, node b)
{
	return a.x*a.y<b.x*b.y; 
}

完整代码:

// P1080
/*
max()
*/
#include 
#define var string
#define SIZE 200010
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;

struct node
{
	int x, y;
};

// comparator
bool operator <(node a, node b)
{
	//return max(b.y, a.x*a.y)
	return a.x*a.y<b.x*b.y; 
}

/*
var read()
{
	var res=0;
	while(1)
	{
		char c=getchar();
		//debug(c)
		if(!('0'<=c && c<='9')) return res;
		res=res*10+c-48;
	}
}

void write(var x)
{
	stack S;
	while(x)
	{
		int r=x%10; x/=10;
		S.push(r);
	}
	while(!S.empty())
	{
		int t=S.top(); S.pop();
		putchar(t+48);
	}
}
*/

var operator *(var x, int y)
{
	int carry=0;
	for(int i=x.size()-1; i>=0; i--)
	{
		int t=x[i]-48;
		// don't forget the carry!
		int tt=t*y+carry; carry=0;
		int res=tt%10; carry+=tt/10;
		x[i]=res+48;
	}
	stringstream ss;
	ss<<carry; string s; ss>>s;
	x=s+x;
	while(x[0]=='0' && x.size())
		x.erase(0, 1);
	if(x.size()==0)
		x='0'+x;
	return x;
}

var operator /(var s, int y)
{
    int i,r=0;
    string ans("");
    if(s=="0") return s;
    for(char &c:s)
    {
        ans.push_back((10*r+c-'0')/y+'0');
        r=(10*r+c-'0')%y;
    }
    for(i=0;ans[i]=='0';++i);
    return ans.substr(i);
}

bool DaYu(string x, string y)
{
	if(x.size()!=y.size())
		return x.size()>y.size();
	return x>y;
}

int main()
{
	int n; cin>>n;
	var kx, ky;
	cin>>kx>>ky;
	
	node a[n];
	for(int i=0; i<n; i++)
	{
		cin>>a[i].x;
		cin>>a[i].y;
	}
	sort(a, a+n);
	var Max="0";
	for(int i=0; i<n; i++)
	{
		//debug(a[i].x)
		//debug(a[i].y)
		//debug(kx)
		var t=kx/a[i].y;
		//debug(t);
		if(DaYu(t, Max)) Max=t;
		kx=kx*a[i].x;
	}
	cout<<Max;

    return 0;
}
例题 2 2 2

AGC023F 01 on Tree

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/565177.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-06
下一篇 2022-04-06

发表评论

登录后才能评论

评论列表(0条)

保存