bef-> NO.26

Veröffentlicht am

[USACO11NOV]高于中位数Above the Median题目描述

Farmer John has lined up his N (1 <= N <= 100,000) cows in a row to measure their heights; cow i has height H_i (1 <= H_i <= 1,000,000,000) nanometers—FJ believes in precise measurements! He wants to take a picture of some contiguous subsequence of the cows to submit to a bovine photography contest at the county fair.

The fair has a very strange rule about all submitted photos: a photograph is only valid to submit if it depicts a group of cows whose median height is at least a certain threshold X (1 <= X <= 1,000,000,000).

For purposes of this problem, we define the median of an array A[0…K] to be A[ceiling(K/2)] after A is sorted, where ceiling(K/2) gives K/2 rounded up to the nearest integer (or K/2 itself, it K/2 is an integer to begin with). For example the median of {7, 3, 2, 6} is 6, and the median of {5, 4, 8} is 5.

Please help FJ count the number of different contiguous subsequences of his cows that he could potentially submit to the photography contest.

给出一串数字，问中位数大于等于X的连续子串有几个。（这里如果有偶数个数，定义为偏大的那一个而非中间取平均）

输入输出格式

输入格式：

* Line 1: Two space-separated integers: N and X.

* Lines 2..N+1: Line i+1 contains the single integer H_i.

输出格式：

* Line 1: The number of subsequences of FJ’s cows that have median at least X. Note this may not fit into a 32-bit integer.

输入输出样例

输入样例#1：

1
2
3
4
5
4 6 
10 
5 
6 
2

输出样例#1：

1
7

说明

FJ’s four cows have heights 10, 5, 6, 2. We want to know how many contiguous subsequences have median at least 6.

There are 10 possible contiguous subsequences to consider. Of these, only 7 have median at least 6. They are {10}, {6}, {10, 5}, {5, 6}, {6, 2}, {10, 5, 6}, {10, 5, 6, 2}.

题解

这道题放到D1T2我就GG了。

对于中位数我们得牢牢抓住一个相对关系。

假如一个区间内， 那么这个区间的中位数就会大于等于x。

所以让前缀和记录i之前有多少个（大于等于x的数 - 小于x的数 ）

然后问题就变成了顺序对，扫描线+树状数组可以完成，时间复杂度为

但是！！别忘了可能出现0，所以权值的位置+上n，而且别忘了1~i整个区间!

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
33
34
35
36
37
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
int bit[maxn<<1] , n , s[maxn] , k;
long long ans;
inline int query(int x){
	int ans = 0;
	for(int i = x ; i ; i -= (i & -i))
		ans += bit[i];
	return ans;
}
inline void update(int x , int v)
{
	for(int i = x ; i <= 2 * n; i += (i & -i))
		bit[i] += v;
}

int main()
{
	scanf("%d%d",&n,&k);
	int x;
	for(int i = 1 ; i <= n ; ++i)
	{
		scanf("%d",&x);
		if(x >= k) s[i] = s[i-1] + 1;
		else s[i] = s[i-1] - 1;
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		ans += query(s[i]+n);
		if(s[i] >= 0) ++ans;
		update(s[i]+n,1);
	}
	printf("%lld",ans);
}

[USACO08NOV]光开关Light Switching

题目描述

Farmer John tries to keep the cows sharp by letting them play with intellectual toys. One of the larger toys is the lights in the barn. Each of the N (2 <= N <= 100,000) cow stalls conveniently numbered 1..N has a colorful light above it.

At the beginning of the evening, all the lights are off. The cows control the lights with a set of N pushbutton switches that toggle the lights; pushing switch i changes the state of light i from off to on or from on to off.

The cows read and execute a list of M (1 <= M <= 100,000) operations expressed as one of two integers (0 <= operation <= 1).

The first kind of operation (denoted by a 0 command) includes two subsequent integers S_i and E_i (1 <= S_i <= E_i <= N) that indicate a starting switch and ending switch. They execute the operation by pushing each pushbutton from S_i through E_i inclusive exactly once.

The second kind of operation (denoted by a 1 command) asks the cows to count how many lights are on in the range given by two integers S_i and E_i (1 <= S_i <= E_i <= N) which specify the inclusive range in which the cows should count the number of lights that are on.

Help FJ ensure the cows are getting the correct answer by processing the list and producing the proper counts.

灯是由高科技——外星人鼠标操控的。你只要左击两个灯所连的鼠标，

这两个灯，以及之间的灯都会由暗变亮，或由亮变暗。右击两个灯所连的鼠

标，你就可以知道这两个灯，以及之间的灯有多少灯是亮的。起初所有灯都是暗的，你的任务是在LZ之前算出灯的亮灭。

输入输出格式

输入格式：

第1 行: 用空格隔开的两个整数N 和M，n 是灯数

第2..M+1 行: 每行表示一个操作, 有三个用空格分开的整数: 指令号, S_i 和E_i

第1 种指令(用0 表示)包含两个数字S_i 和E_i (1 <= S_i <= E_i <= N), 它们表示起

始开关和终止开关. 表示左击

第2 种指令(用1 表示)同样包含两个数字S_i 和E_i (1 <= S_i <= E_i <= N), 不过这

种指令是询问从S_i 到E_i 之间的灯有多少是亮着的.

输出格式：

输入输出样例

输入样例#1：

1
2
3
4
5
6
4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

输出样例#1：

1
2
1
2

说明

img

原题时间限制为2s，内存限制为16M

题解

一道线段树基础题，标记维护什么的不难。

除了把pushup写成+=一切都好

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
int sum[maxn<<2] , xr[maxn<<2] , n , m , x , y , op;
inline void pushup(int Node){
	sum[Node] = sum[ls(Node)] + sum[rs(Node)];
}
inline void pushdown(int Node , int ln , int rn){
	if(xr[Node]){
		sum[ls(Node)] = ln - sum[ls(Node)];
		sum[rs(Node)] = rn - sum[rs(Node)];
		xr[ls(Node)] ^= xr[Node];
		xr[rs(Node)] ^= xr[Node];
		xr[Node] ^= 1;
	}
}
inline void update(int L , int R , int l , int r , int Node)
{
	if(L <= l && r <= R)
	{
		xr[Node] ^= 1;
		sum[Node] = (r-l+1) - sum[Node];
		return;
	}
	int mid = l + r >> 1;
	pushdown(Node , mid - l + 1 , r - mid);
	if(L <= mid) update(L , R , l , mid , ls(Node));
	if(R > mid)	update(L , R , mid + 1 , r , rs(Node));
	pushup(Node);
}
int query(int L , int R , int l , int r , int Node){
	if(L <= l && r <= R){
		return sum[Node];
	}
	int mid = l + r >> 1 , ans = 0;
	pushdown(Node , mid - l + 1 , r - mid);
	if(L <= mid) ans += query(L , R , l , mid , ls(Node));
	if(R > mid) ans += query(L , R , mid + 1 , r , rs(Node));
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= m ; ++i)
	{
		scanf("%d",&op);
		if(!op){
			scanf("%d%d",&x,&y);
			update(x,y,1,n,1);
		}
		else{
			scanf("%d%d",&x,&y);
			printf("%d\n",query(x,y,1,n,1));
		}
	}
}

[USACO10OCT]汽水机Soda Machine

题意翻译

为了满足fj所有的N(1<=n<=50000)头奶牛的需求，fj新买了一台汽水机。他想找到一个最完美的位置来安放它。

奶牛的牧场可以被表示为一个一维数轴，第i个奶牛被放牧的区间是[Ai…Bi]（包含端点），fj可以把汽水机放在[1..1,000,000,000]。

因为奶牛们都懒得要死，她们想尽可能的少移动。她们希望汽水机被放在自己的放牧区间内。

遗憾的是，fj并不总能满足所有奶牛的要求，所以他想请你帮忙算出他能满足的奶牛数目

题目描述

To meet the ever-growing demands of his N (1 <= N <= 50,000) cows, Farmer John has bought them a new soda machine. He wants to figure out the perfect place to install the machine.

The field in which the cows graze can be represented as a one-dimensional number line. Cow i grazes in the range A_i..B_i (1 <= A_i <= B_i; A_i <= B_i <= 1,000,000,000) (a range that includes its endpoints), and FJ can place the soda machine at any integer point in the range 1..1,000,000,000. Since cows are extremely lazy and try to move as little as possible, each cow would like to have the soda machine installed within her grazing range.

Sadly, it is not always possible to satisfy every cow’s desires. Thus FJ would like to know the largest number of cows that can be satisfied.

To demonstrate the issue, consider four cows with grazing ranges 3..5, 4..8, 1..2, and 5..10; below is a schematic of their grazing ranges:

1
2
3
4
5
1   2   3   4   5   6   7   8   9  10  11  12  13
|---|---|---|---|---|---|---|---|---|---|---|---|-...
        aaaaaaaaa
            bbbbbbbbbbbbbbbbb
ccccc           ddddddddddddddddddddd

As can be seen, the first, second and fourth cows share the point 5, but the third cow’s grazing range is disjoint. Thus, a maximum of 3 cows can have the soda machine within their grazing range.

输入输出格式

输入格式：

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains two space-separated integers: A_i and B_i

输出格式：

* Line 1: A single integer representing the largest number of cows whose grazing intervals can all contain the soda machine.

输入输出样例

输入样例#1：

1
2
3
4
5
4 
3 5 
4 8 
1 2 
5 10

输出样例#1：

1
3

说明

If the soda machine is placed at location 5, cows 1, 2, and 4 can be satisfied. It is impossible to satisfy all four cows.

题解

显然由于坐标太大，需要离散化。

那怎么找数轴上被覆盖次数最多的点呢？这就是一个扫描线的思想，显然被覆盖次数最多的点一定由两个离散化的端点构成。

因此我们把点记录左右端点属性按照大小离散化

然后还原线段在线段树上做区间覆盖，

之后对每个离散化的点查询被覆盖次数即可，正确性已经说明：被覆盖次数最多的区间必定由两个端点构成，否则反证易知这个区间内还有其他点和左端点构成被覆盖次数最多的区间，由扫描线的原理可知这是不会出现的。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define maxn 100005
struct Node{
	int v , type , k;
	bool operator <(const Node& x)const{
		return v < x.v;
	}
}p[maxn];
int L[maxn] , R[maxn] , sum[maxn<<2] , add[maxn<<2] , ans , n , cnt , tot;
inline void pushup(int Node){
	sum[Node] = sum[ls(Node)] + sum[rs(Node)];
}
inline void pushdown(int Node , int ln , int rn)
{
	if(add[Node]){
		sum[ls(Node)] += ln * add[Node];
		sum[rs(Node)] += rn * add[Node];
		add[ls(Node)] += add[Node];
		add[rs(Node)] += add[Node];
		add[Node] = 0;
	}
}
void update(int L , int R , int l , int r , int Node , int v)
{
	if(L <= l && r <= R){
		sum[Node] += (r-l+1) * v;
		add[Node] += v;
		return;
	}
	int mid = l + r >> 1;
	if(L <= mid)	update(L , R , l , mid , ls(Node) , v);
	if(R > mid) 	update(L , R , mid + 1 , r , rs(Node) , v);
	pushup(Node);
}
int query(int L , int R ,  int l , int r , int Node)
{
	if(l == r){
		return sum[Node];
	}
	int mid = l + r >> 1 , ans = 0;
	pushdown(Node , mid - l + 1 , r - mid);
	if(L <= mid) ans += query(L , R , l , mid, ls(Node));
	if(R > mid) ans += query(L , R , mid + 1 , r , rs(Node));
	return ans;
}
int main()
{
	scanf("%d",&n);
	int x , y;
	for(int i = 1 ; i <= n ; ++i)
	{
		scanf("%d%d",&x,&y);
		p[++cnt].v = x , p[cnt].type = 0 , p[cnt].k = i;
		p[++cnt].v = y , p[cnt].type = 1 , p[cnt].k = i;
	}
	std::sort(p+1,p+cnt+1);
	for(int i = 1 ; i <= cnt ; ++i)
	{
		if(p[i].type){
			if(p[i].v == p[i-1].v)	R[p[i].k] = tot;
			else R[p[i].k] = ++tot;
		}
		else{
			if(p[i].v == p[i-1].v)	L[p[i].k] = tot;
			else L[p[i].k] = ++tot;
		}
	}

	for(int i = 1 ; i <= n ; ++i)
		update(L[i] , R[i] , 1 , tot , 1 , 1);
	for(int i = 1; i <= tot ; ++i)
		ans = std::max(ans , query(i,i,1,tot,1));
	printf("%d",ans);
}

P2345 奶牛集会

题目背景

MooFest, 2004 Open

题目描述

约翰的N 头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很

多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i 头奶牛的坐标为Xi，没有两头奶牛的坐标是相同的。奶牛们的叫声很大，第i 头和第j 头奶牛交流，会发出max{Vi; Vj}×|Xi − Xj | 的音量，其中Vi 和Vj 分别是第i 头和第j 头奶牛的听力。假设每对奶牛之间同时都在说话，请计算所有奶牛产生的音量之和是多少。

输入输出格式

输入格式：

• 第一行：单个整数N，1 ≤ N ≤ 20000

• 第二行到第N + 1 行：第i + 1 行有两个整数Vi 和Xi，1 ≤ Vi ≤ 20000; 1 ≤ Xi ≤ 20000

输出格式：

• 单个整数：表示所有奶牛产生的音量之和

输入输出样例

输入样例#1：

1
2
3
4
5
4
3 1
2 5
2 6
4 3

输出样例#1：

1
57

题解

独立切题的感觉真好。

这道题分析了一波，感觉数据真弱emmmm ， 要我出数据

不过

有些麻烦。

我们直接说上述的强化版数据做法

分析一下给定的统计要求，我们发现可以分别统计。

考虑每个数的v对答案的贡献，即当前v是两者中较大的，我们从左往右扫描线可以算出它左边权值比它小的坐标和，然后扫描线再从右向左计算它右边的坐标和，对于左边我们这么计算对答案的贡献。

设左边有num个v比它小的，查询的坐标和是sum

右边只需要反过来。。

自己推一推完事了。

注意不要算重！

注意要开long long！

主要还是一个扫描线降维的思想。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 100005
long long bit[2][maxn] , n;
long long ans;
struct Node{
	long long v , x;
	bool operator < (const Node& p)const{
		return x < p.x;
	}
}p[maxn];
inline long long query(int x , int op)
{
	long long ans = 0;
	for(int i = x ; i ; i -= (i & -i))
		ans += bit[op][i];
	return ans;
}
inline void update(int x , int v , int op)
{
	for(int i = x ; i <= 20000 ; i += (i & -i))
		bit[op][i] += v;
}
int main()
{
	scanf("%lld",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%lld%lld",&p[i].v,&p[i].x);
	std::sort(p+1,p+n+1);
	for(int i = 1 ; i <= n ; ++i)
	{
		long long k = query(p[i].v , 0) , num = query(p[i].v , 1);
		ans += num * p[i].x * p[i].v - k * p[i].v;
		update(p[i].v , p[i].x , 0) , update(p[i].v , 1 , 1);
	}
	std::memset(bit,0,sizeof(bit));
	for(int i = n ; i >= 1 ; --i)
	{
		long long k = query(p[i].v - 1, 0) , num = query(p[i].v - 1 , 1);
		ans += k * p[i].v - num * p[i].x * p[i].v; 
		update(p[i].v , p[i].x ,0) , update(p[i].v , 1 , 1);
	}
	printf("%lld",ans);
}

[USACO15DEC]Fruit Feast 水果盛宴

题意翻译

现在Bessie的饱食度为 00 ，她每吃一个橙子，饱食度就会增加 AA ；每吃一个柠檬，饱食度就会增加 BB 。Bessie还有一次喝水的机会，如果Bessie喝水前饱食度为 xx ，喝水后饱食度会变为 \left\lfloor\dfrac{x}{2}\right\rfloor⌊2x⌋ 。
Bessie的饱食度不能超过 TT ，否则肚子会爆炸。试求Bessie的饱食度最大能达到多少。

Translated by @Planet6174

题目描述

Bessie has broken into Farmer John’s house again! She has discovered a pile of lemons and a pile of oranges in the kitchen (effectively an unlimited number of each), and she is determined to eat as much as possible.

Bessie has a maximum fullness of TT (1 ≤ T ≤ 5,000,000)(1≤T≤5,000,000). Eating an orange increases her fullness by AA, and eating a lemon increases her fullness by BB (1 ≤ A,B ≤ T1≤A,B≤T). Additionally, if she wants, Bessie can drink water at most one time, which will instantly decrease her fullness by half (and will round down).

Help Bessie determine the maximum fullness she can achieve!

输入输出格式

输入格式：

The first (and only) line has three integers TT, AA, and BB.

输出格式：

A single integer, representing the maximum fullness Bessie can achieve.

输入输出样例

输入样例#1：

1
8 5 6

输出样例#1：

1
8

说明

Problem credits: Nathan Pinsker

题解

写一道水搜索，结果还被卡一个点，仔细一看确实是我写错了。显然要么喝水后吃，但是不能吃了再喝水，那意味着可能吃了就撑死了。

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
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define maxT 5000005
#define INF -0x7ffffff
bool f[maxT][2] ;
int n , a  , b , ans = -0x7fffff;
void dfs(int cur , bool flag)
{
	if(cur > n){
//		if(!flag) dfs((cur + a) / 2 , true) , dfs((cur + b) / 2 , true);
		return;
	}else ans = std::max(ans , cur); 
	if(f[cur][flag])	return;
	f[cur][flag] = true;
	dfs(cur + a , flag);
	dfs(cur + b , flag);
	if(!flag)	dfs(cur / 2 + a , true) , dfs(cur / 2 + b , true);
}
int main()
{
	scanf("%d%d%d",&n,&a,&b);
	dfs(0,0);
	printf("%d",ans);
}

其实可以用完全背包来做，懒得写了。

[USACO08NOV]守护农场Guarding the Farm.

题意翻译

农夫John的农场里有很多小山丘，他想要在那里布置一些保镖去保卫他的那些相当值钱的奶牛们。

他想知道如果在一座小山丘上布置一名保镖的话，他最少总共需要招聘多少名保镖。他现在手头有一个用数字矩阵来表示地形的地图。这个矩阵有N行（1＜N≤700)和M列( 1＜M≤ 700) 。矩阵中的每个元素都有一个值H_ij（0≤H_ij≤10000）来表示该地区的海拔高度。

小山丘的定义是：若地图中一个元素所邻接的所有元素都比这个元素高度要小（或它邻接的是地图的边界），则该元素和其周围所有按照这样顺序排列的元素的集合称为一个小山丘。这里邻接的意义是：若一个位置的横纵坐标与另一个位置的横纵坐标相差不超过1，则称这两个元素邻接，比如某个非边界点的位置有8个相邻点：上、下、左、右、左上、右上、左下、右下。

请你帮助他统计出地图上最少且尽量高的小山丘数量。

题目描述

The farm has many hills upon which Farmer John would like to place guards to ensure the safety of his valuable milk-cows.

He wonders how many guards he will need if he wishes to put one on top of each hill. He has a map supplied as a matrix of integers; the matrix has N (1 < N <= 700) rows and M (1 < M <= 700) columns. Each member of the matrix is an altitude H_ij (0 <= H_ij <= 10,000). Help him determine the number of hilltops on the map.

A hilltop is one or more adjacent matrix elements of the same value surrounded exclusively by either the edge of the map or elements with a lower (smaller) altitude. Two different elements are adjacent if the magnitude of difference in their X coordinates is no greater than 1 and the magnitude of differences in their Y coordinates is also no greater than 1.

输入输出格式

输入格式：

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 describes row i of the matrix with M

space-separated integers: H_ij

输出格式：

* Line 1: A single integer that specifies the number of hilltops

输入输出样例

输入样例#1：

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

输出样例#1：

1
3

说明

There are three peaks: The one with height 4 on the left top, one of the points with height 2 at the bottom part, and one of the points with height 1 on the right top corner.

题解

一个破搜索我还整出了新的花样，我想的是从一个点开始单调升降都是可行的，结果写疵了。

然后按高度排序一遍A了

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define maxn 705
int s[maxn][maxn] , n , m , ans , dx[] = {0,0,1,1,1,-1,-1,-1} , dy[] = {1,-1,1,0,-1,1,0,-1} , tot;
bool vis[maxn][maxn];
struct Node{
	int x , y , h;
	bool operator < (const Node& oty) const{
		return h > oty.h;
	}
}p[maxn*maxn];
inline void bfs(int x , int y)
{
	++ans;
	std::queue<Node> q;
	q.push((Node){x,y,s[x][y]});
	while(!q.empty())
	{
		int k = q.front().x , p = q.front().y , h = q.front().h;
		q.pop();
		for(int i = 0 ; i < 8 ; ++i)
		{
			int xx = k + dx[i] , yy = p + dy[i] , hh = s[xx][yy];
			if(vis[xx][yy] || hh > h || xx < 1 || xx > n || yy < 1 || yy > m)	continue;
			vis[xx][yy] = true;
			q.push((Node){xx,yy,hh});
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n ; ++i)
		for(int j = 1 ; j <= m ; ++j)
			scanf("%d",&s[i][j]) , p[++tot].x = i , p[tot].y = j , p[tot].h = s[i][j] ;
	std::sort(p+1,p+tot+1);
	for(int i = 1 ; i <= tot ; ++i)
	{
		int x = p[i].x , y = p[i].y , h = p[i].h;
		if(vis[x][y])	continue;
		bfs(x,y);
	}
	printf("%d",ans);
}

[USACO09OPEN]工作调度Work Scheduling

题意翻译

约翰有太多的工作要做。为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。 他的工作日从0时刻开始，有10^9个单位时间。在任一时刻，他都可以选择编号1~N的N(1 <= N <= 10^6)项工作中的任意一项工作来完成。 因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有N个工作，虽然还是有可能。 对于第i个工作，有一个截止时间D_i(1 <= D_i <= 10^9)，如果他可以完成这个工作，那么他可以获利P_i( 1<=P_i<=10^9 ). 在给定的工作利润和截止时间下，约翰能够获得的利润最大为多少.

题目描述

Farmer John has so very many jobs to do! In order to run the farm efficiently, he must make money on the jobs he does, each one of which takes just one time unit.

His work day starts at time 0 and has 1,000,000,000 time units (!). He currently can choose from any of N (1 <= N <= 100,000) jobs

conveniently numbered 1..N for work to do. It is possible but

extremely unlikely that he has time for all N jobs since he can only work on one job during any time unit and the deadlines tend to fall so that he can not perform all the tasks.

Job i has deadline D_i (1 <= D_i <= 1,000,000,000). If he finishes job i by then, he makes a profit of P_i (1 <= P_i <= 1,000,000,000).

What is the maximum total profit that FJ can earn from a given list of jobs and deadlines? The answer might not fit into a 32-bit integer.

输入输出格式

输入格式：

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains two space-separated integers: D_i and P_i

输出格式：

* Line 1: A single number on a line by itself that is the maximum possible profit FJ can earn.

输入输出样例

输入样例#1：

1
2
3
4
3 
2 10 
1 5 
1 7

输出样例#1：

1
17

说明

Complete job 3 (1,7) at time 1 and complete job 1 (2,10) at time 2 to maximize the earnings (7 + 10 -> 17).

题解

这是一道有一定难度的贪心，尤其是在证明它的正确性时。

首先明确贪心的子问题是对每一项加进来后的最优值。

然后对于每加进来一项，有两种可能：

总时间不够了！这时候由于这种类似扫描线的枚举，我们只需要去掉一项，显然我们把前面某一个最小的去掉后让被去掉后面的都在前一时刻做，把当前项加进来，就完成了当前的最优状态。

显然这种贪心用堆维护状态

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
33
34
35
36
37
38
39
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#define maxn 1000005
struct Node{
	int v , t;
	bool operator < (const Node& x) const{
		return v > x.v;
	}
}p[maxn];
int n;
long long ans;
std::priority_queue<Node> q;
bool cmp(Node x , Node y){
	return x.t < y.t;
}
int main()
{
//	freopen("creep.in","r",stdin);
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d%d",&p[i].t,&p[i].v);
	std::sort(p+1,p+n+1,cmp);
	for(int i = 1 ; i <= n ; ++i)	
	{
		if(p[i].t > q.size()){
			ans += p[i].v;
			q.push((Node){p[i].v,p[i].t});
		}
		else if(p[i].v > q.top().v){
			ans += p[i].v - q.top().v;
			q.pop();
			q.push((Node){p[i].v,p[i].t});
		}
	}
	printf("%lld",ans);
}

[USACO08OCT]打井Watering Hole

题目背景

John的农场缺水了！！！

题目描述

Farmer John has decided to bring water to his N (1 <= N <= 300) pastures which are conveniently numbered 1..N. He may bring water to a pasture either by building a well in that pasture or connecting the pasture via a pipe to another pasture which already has water.

Digging a well in pasture i costs W_i (1 <= W_i <= 100,000).

Connecting pastures i and j with a pipe costs P_ij (1 <= P_ij <= 100,000; P_ij = P_ji; P_ii=0).

Determine the minimum amount Farmer John will have to pay to water all of his pastures.

POINTS: 400

农民John 决定将水引入到他的n(1<=n<=300)个牧场。他准备通过挖若

干井，并在各块田中修筑水道来连通各块田地以供水。在第i 号田中挖一口井需要花费W_i(1<=W_i<=100,000)元。连接i 号田与j 号田需要P_ij (1 <= P_ij <= 100,000 , P_ji=P_ij)元。

请求出农民John 需要为使所有农场都与有水的农场相连或拥有水井所需要的钱数。

输入输出格式

输入格式：

第1 行为一个整数n。

第2 到n+1 行每行一个整数，从上到下分别为W_1 到W_n。

第n+2 到2n+1 行为一个矩阵，表示需要的经费（P_ij）。

输出格式：

只有一行，为一个整数，表示所需要的钱数。

输入输出样例

输入样例#1：

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

输出样例#1：

1
9

说明

John等着用水，你只有1s时间！！！

题解

一道非常非常好的最小生成树的题。假如没认真学过prim的原理你是做不出来的（虽然从原理上来说必须用n^2的prim，因为这道题的每个点最初的dis就是点权），可以证明也可以很好地理解这种做法的正确性。

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
#include<cstdio>
    using namespace std;
    int n,dst[305],ans,cst[305][305];bool vis[305];
    inline int read(){
        int ret=0;char ch=getchar();
        while(ch<'0'||ch>'9') ch=getchar();
        while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
        return ret;
    }
    int main(){
        n=read();
        for(int i=1;i<=n;i++) dst[i]=read();
        for(int i=1;i<=n;i++)
          for(int j=1;j<=n;j++) cst[i][j]=read();
        int k,min_x;
        for(int i=1;i<=n;i++){
            min_x=1<<30;
            for(int j=1;j<=n;j++)if(!vis[j]&&dst[j]<min_x) min_x=dst[j],k=j;
            ans+=min_x,vis[k]=1;
            for(int j=1;j<=n;j++)if(!vis[j]&&cst[k][j]<dst[j]) dst[j]=cst[k][j];
        }
        printf("%d\n",ans);
        return 0;
}

然后为了处理更大的数据，可以建立虚点然后Kruskal（直接用这种做法的表示不懂脑回路）

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
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 305
struct Node{
	int f , t , dis;
	bool operator < (const Node& x)const {
		return dis < x.dis;
	}
}p[maxn*maxn];
int cnt , n , mst , f[maxn] , x;
int find(int x){
	if(f[x] != x)	return f[x] = find(f[x]);
	return f[x];
}
int main()
{
	scanf("%d",&n);
	for(int i  = 1 ; i <= n ; ++i){
		int x;
		scanf("%d",&x);
		p[++cnt].f = 0 , p[cnt].t = i , p[cnt].dis = x;
	}
	for(int i = 1 ; i <= n ; ++i){
		for(int j = 1 ; j <= n ; ++j){
			scanf("%d",&x);
			if(i == j)	continue;
			p[++cnt].f = i , p[cnt].t = j , p[cnt].dis = x;
		}
	}
	std::sort(p+1,p+cnt+1);
	for(int i = 0 ; i <= n ; ++i)
		f[i] = i;
	for(int i = 1 ; i <= cnt ; ++i){
		int ff = p[i].f , t = p[i].t;
		int fx = find(ff) , fy = find(t);
		if(fx != fy){
			mst += p[i].dis;
			f[fx] = fy;
		}
	}
	printf("%d",mst);
}

但是Kruskal似乎没有任何道理，无法证明正确性。。事实上这个题有理有据的做法就是Prim，也可以堆优化

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int,int> pir;
const int N=5000+10;
const int M=200000+10;

int first[N],tot;
int vis[N],dis[N],n,m;
priority_queue <pir,vector<pir>,greater<pir> >q;
struct edge
{
    int v,w,next;
} e[M*2];

void add_edge(int u,int v,int w)
{
    e[tot].v=v;
    e[tot].w=w;
    e[tot].next=first[u];
    first[u]=tot++;
}
void init()
{
    mem(first,-1);
    tot=0;
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d",&dis[i]);
}
void prim()
{
    int cnt=0,sum=0;
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty()&&cnt<n)
    {
        int d=q.top().first,u=q.top().second;
        q.pop();
        if(!vis[u])
        {
            cnt++;
            sum+=d;
            vis[u]=1;
            for(int i=first[u]; ~i; i=e[i].next)
                if(e[i].w<dis[e[i].v])
                {
                    dis[e[i].v]=e[i].w;
                    q.push(make_pair(dis[e[i].v],e[i].v));
                }
        }
    }
    if(cnt==n) printf("%d\n",sum);
    else puts("orz");
}
int main()
{
    int u,v,w;
    init();
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w);
        add_edge(v,u,w);
    }
    prim();
    return 0;
}