[2018.04.17][水][日志][6][#171~#181][贪心算法][已经丧心病狂][背景->][最虚伪的算法]

[背景]

    在某日和某大佬们一起举行的ACM上，我们小队面对一道多重背包题跪了...凉凉（可喜的是我AC了C，G两题)。

    在面对大佬们的D题上，我们使用了，啊不，第一次使用了贪心算法，奇迹般的通过了九个点（死在了第十个点上）

[贪心算法]

    1.

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑（特别是涉及剩余值时的规划），他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

    2.贪心的宗旨：骗分。

[然后上题目]

#173.三值排序

题目描述
排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌排序的时候。在这个任务中可能的值只有三种1，2和3。我们用交换的方法把他排成升序的。 写一个程序计算出，给定的一个1,2,3组成的数字序列，排成升序所需的最少交换次数。 
输入格式 第 1 行： 奖牌个数N (1 <= N <= 1000) 第 2 行到第 N+1 行: 每行一个数字，表示奖牌。共N行。（1..3） 
输出格式 共一行，一个数字。表示排成升序所需的最少交换次数。

[分析]

很典型的贪心，即统计1，2，3分别出现的次数

然后我们就确定了1，2，3分别应该出现在哪里。

接下来就是贪心地搜索他们应该出现在哪里了（让1应该出现的位子不留2，3，并让2，3，尽可能靠近他们应该处在的位置).

很好，这个东西已经差不多了。

最后我们要考虑的是2和3中的叛徒。

很好，AC

#174.修理牛棚

这道题需要逆向思维，不用去想连木板，而是去找最大的空隙。

#177 穿墙人

题目描述
穿墙术是现代魔术表演中常见的一个节目。魔术中的穿墙人可以穿过预先设计好的若干道墙。所有的墙被安置在一个网格区域中，如图所示，‘？’表示墙所占据的网格，所有的墙都水平放置，宽度为1个单位，但长度可能不同。任何两道墙不会相互重叠，即任何一个‘？’不能同时属于两道或两道以上的墙。穿墙人的能量有限，每次表演至多只能穿过k道墙。 表演开始时，主持人让观众任选网格的某一列，然后穿墙人开始沿着此列从网格的上端穿过中间的每一道墙到达网格的底部。但如果观众所选择的那一列中有大于k道墙，则穿墙人的表演会失败。 例图所示，如果k=3，则穿墙人可以自上而下地穿过除第6列外的任何列，因为只有第6列需要穿越4道墙，但穿墙人在同一列上最多只能穿过3道墙。
当所有的墙给出之后，如果知道穿墙人当前的能量K，我们希望移去最少数目的墙，才能使得穿墙人能够穿越任何一列。 对于图中的例子，如果k=3，穿墙人无法穿越第6列，但是只要把第3行的墙移去（不唯一），则穿墙人就可以穿过任意一列。因此对于这个例子最少需要移去1道墙。
输入格式
第一行是用空格隔开的两个整数n和k，其中1 ≤ n ≤ 100，0 ≤ k ≤ 100；n表示墙的数目，k表示穿墙人在同一列上最多能穿过多少道墙。接下来有n行，每行是用空格隔开的四个整数x1, y1, x2, y2，其中(x1, y1)和(x2, y2)分别表示一道墙的两个端点（注意，根据题意，一定有y1=y2）。x, y坐标的范围为[0, 100]，左上角的坐标定为(0, 0)。
输出格式
只包含一个整数，即为了让穿墙人能够穿越任意一列所需要移去的最少的墙的数目。
样例数据
input
7 3 
0 0 3 0 
6 1 8 1
2 3 6 3 
4 4 6 4 
0 5 1 5 
5 6 7 6 
1 7 3 7
output
1
数据规模与约定
保证a,b≤109
a,b≤109
时间限制：1s

空间限制：256MB

很好，这是一道贪心题！！！！！

首先就是右值排序，也就是对线段进行x值末端的排序。

然后就是虚伪的东西

#include<bits/stdc++.h>
using namespace std;

struct cow
{
	int left,right;
}a[110];

bool mycmp(cow x,cow y)
{
	if(x.right!=y.right)
		return x.right<y.right;
	else
		return x.left>y.left; 
}

int main(void)
{
	int n,k;
	cin>>n>>k;
	int a1,a2,a3,a4;
	for(int i=1;i<=n;i++)
	{
		cin>>a1>>a2>>a3>>a4;
		a[i].left=min(a1,a3);
		a[i].right=max(a3,a1);
	}
	
	sort(a+1,a+n+1,mycmp);
	
	int f[1000]={};
	int s=0;
	for(int i=1;i<=n;i++)
		for(int j=a[i].left;j<=a[i].right;j++)
		{
			if(f[j]+1<=k)
				f[j]++;
			else
			{
				s++;
				for(int k=j-1;k>=a[i].left;k--)
					f[j]--;
				break;
	  	    }
	  }
	cout<<s<<endl;
	return 0;
}

#175 巧克力{HAOI}

[背景]

    本来打算在图书馆里慢慢做的，可是，忽然发现是很容易看出这道题其实是贪心，只要用不等式慢慢证就发现了（一脸虚伪）。

[题干]

题目描述
       有一块n×m的矩形巧克力，准备将它切成n*m块。巧克力上共有n-1条横线和m-1条竖线，你每次可以沿着其中的一条横线或竖线将巧克力切开，无论切割的长短，沿着每条横线切一次的代价依次为y1，y2，…，yn-1，而沿竖线切割的代价依次为x1，x2，…，xm-1。例如，对于下图6×

×4的巧克力，我们先沿着三条横线切割，需要3刀，得到4条巧克力，然后再将这4条巧克力沿竖线切割，每条都需要5刀，则最终所花费的代价为y1+y2+y3+4*(x1+x2+x3+x4+x5)。 当然，上述简单切法不见得是最优切法，那么怎样切割该块巧克力，花费的代价最少呢？

输入格式
第一行为两个整数n和m。 接下来n-1行，每行一个整数，分别代表x1，x2，…，xn-1。 接下来m-1行，每行一个整数，分别代表y1，y2，…，ym-1。
输出格式
输出一整数，为切割巧克力的最小代价。 
样例数据
input
6 4
2
1
3
1
4
4
1
2
output
42
数据规模与约定
时间限制：1s
1s
空间限制：256MB
256MB
注释

30%的数据，n<=100,m<=100 100%的数据，n<=10000，m<=10000

[分析]

这道题很虚伪，因为代价的加成公式是一样的，所以，为了避免大代价被多次叠加从而GG，因此要优先考虑删除大代价值，转而让小的代价累计多一点

接下来就是所谓的搜索了，这里用上了归并排序的思想；

很好，这里有个让两位大佬疑惑的问题：为什么要优先比较切掉单段的代价而不是权重（单位代价*段数）的代价呢？

答：防止在以后的乘法中那个被忽略的单位大值爆炸。

#include<bits/stdc++.h>
using namespace std;

struct note
{
	int weight;
};

note x[10010]={};
note y[10010]={};
int m=0,n=0;
int ans=0;

bool mycmp(note x,note y)
{
	return (x.weight>y.weight);
}

int main(void)
{
	std::ios::sync_with_stdio(false);
	cin>>n>>m;
	n--;
	m--;

	for(int i=1;i<=n;i++)
	{
		cin>>x[i].weight;
	}

	for(int j=1;j<=m;j++)
	{
		cin>>y[j].weight;
	}

	sort(x+1,x+n+1,mycmp);
	sort(y+1,y+m+1,mycmp);

	int tx=1;
	int ty=1;
	int co=0;
	for(int i=1;i<=m+n;i++)
	{
		if(x[tx].weight>y[ty].weight)
		{
			ans+=x[tx].weight*ty;
			tx++;
			co++;
		}
		else if(x[tx].weight<=y[ty].weight)
		{
			ans+=y[ty].weight*tx;
			ty++;
			co++;
		}

		if(co>=m+n)
			break;
	}

	cout<<ans<<endl;
	return 0;
}