贪心 学习笔记

简介

贪心的一种方法，那就是写一个 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(bi​A​,bj​ai​A​)⩽max(bj​A​,bi​aj​A​)

( 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}) (bi​A​⩽bj​A​orbi​A​⩽bi​aj​A​)and(bj​ai​A​⩽bj​A​orbj​ai​A​⩽bi​aj​A​)

( 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) (bj​⩽bi​or1⩽aj​)and(ai​⩽1orai​bi​⩽aj​bj​)

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

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

因此，这个式子是否为 1 1 1 取决于 a i b i ⩽ a j b j a_ib_i\leqslant a_jb_j ai​bi​⩽aj​bj​。

这样，如果不需要交换，满足的条件应为 a i b i ⩽ a j b j a_ib_i\leqslant a_jb_j ai​bi​⩽aj​bj​。

也就是这一段。

// 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