Post 8

Veröffentlicht am | Edited on

你知道人类最大的武器是什么吗？是豁出去的决心。

数学小周考又炸锅了。。。本来能全对的选择填空扣了20分，结果卡了及格线qwq

数学老师碰到我还鼓励我下次稳一点争取考140。。

回去买本数学题和物理题了，早点准备月考，感觉那些高考不考的科学的太好的确没什么意义。

来机房先过了道二分答案的水题。。

「一本通 1.2 例 1」愤怒的牛

题目描述

原题来自：USACO 2005 Feb. Gold

农夫约翰建造了一座有 nn 间牛舍的小屋，牛舍排在一条直线上，第 ii 间牛舍在 x_ixi 的位置，但是约翰的 mm 头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。John 决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？

输入格式

第一行用空格分隔的两个整数 nn 和 mm；

第二行为 nn 个用空格隔开的整数，表示位置 x_ixi。

输出格式

输出仅一个整数，表示最大的最小距离值。

样例

样例输入

1
2
5 3
1 2 8 4 9

样例输出

1
3

样例解释

把牛放在 11, 44 ,88 这样最小距离是 33 。

数据范围与提示

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
int x[maxn] , n , m;
inline bool check(int ans)
{
	int tot = 0 , cur = 0;
	for(int i = 2 , cur = 0; i <= n ; ++i)
	{
		cur += x[i] - x[i-1];
		if(cur >= ans) cur = 0 , ++tot;
	}
	if(tot >= m - 1)	return true;
	else return false;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&x[i]);
	std::sort(x+1,x+n+1);
	int l = 0 , r = 100000000 , ans = 0;
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(check(mid)) ans = mid , l = mid + 1;
		else r = mid - 1;
	}
	printf("%d",ans);
}

[USACO14JAN]记录奥林比克

题目描述

Being a fan of all cold-weather sports (especially those involving cows),Farmer John wants to record as much of the upcoming winter Moolympics as possible.

The television schedule for the Moolympics consists of N different programs(1 <= N <= 150), each with a designated starting time and ending time. FJ has a dual-tuner recorder that can record two programs simultaneously.

Please help him determine the maximum number of programs he can record in total.

农民约翰热衷于所有寒冷天气的运动（尤其是涉及到牛的运动）， 农民约翰想录下尽可能多的电视节目。 为moolympics电视时间表由N个不同的节目 （1 < = n＝150），每个具有指定的开始时间和结束时间。FJ 有一个双调谐器录音机，可以同时录制两个节目。 请帮助他确定他能录制的节目的最大数量。

输入输出格式

输入格式：

* Line 1: The integer N.

* Lines 2..1+N: Each line contains the start and end time of a single program (integers in the range 0..1,000,000,000).

第1行：整数n。 第2行.. 1 + n：每行包含单个的开始和结束时间 程序（范围为0…1000000000的整数）。

输出格式：

* Line 1: The maximum number of programs FJ can record.

仅一行，节目FJ可以记录的最大数量。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
6
0 3
6 7
3 10
1 5
2 8
1 9

输出样例#1：

1
4

说明

INPUT DETAILS:

The Moolympics broadcast consists of 6 programs. The first runs from time 0 to time 3, and so on.

OUTPUT DETAILS:

FJ can record at most 4 programs. For example, he can record programs 1 and 3 back-to-back on the first tuner, and programs 2 and 4 on the second tuner.

Source: USACO 2014 January Contest, Silver

题解

想出一个感觉很合理的贪心策略似乎并不难。

贪心需要满足无后效性，因此在正着枚举的时候右端点必须单调增，所以排序。

然后能让第一个听就让第一个听，不然就尽量让第二个听。

为什么这个简单的贪心策略是正确的呢？

假设只有一个显然是正确的，只需要考虑决策的包容性。

假设现在有两个，如果当前物品可以放进第一个，那么按上述理论放入即可。

假设不能放入第一个但是能放入第二个，如果不放后面放入第二个的结束时间会更晚，显然不是最优决策。

又因为我们始终尽量放入第一个，所以R1>=R2，那么显然放入R1不会比R2更差。

这题实际上可以推广到k个。

感觉我需要从进阶指南上学习严谨的贪心证明方法。

时间复杂度

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 305
struct Node{
	int b , e;
	bool operator<(const Node& x)const{
		if(e == x.e) return b > x.b;
		return e < x.e;
	}
}p[maxn];
int n , ans;
bool vis[maxn];
int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
 		scanf("%d%d",&p[i].b,&p[i].e);
	std::sort(p+1,p+n+1);
	int R1 = -0x7ffff , R2 = -0x7ffff;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(p[i].b >= R1) R1 = p[i].e , ++ans;
		else if(p[i].b < R1 && p[i].b >= R2)	R2 = p[i].e , ++ans;
		if(R1 < R2) std::swap(R1,R2);
		//printf("%d %d %d %d\n",p[i].b,p[i].e,R1,R2);
	}
	printf("%d",ans);
}