S2OJ-1470饥饿的小鸟（river）题解

题解►S2OJ , , 评论

题面

题目描述

一群饥饿的小鸟，要到河对岸吃东西。河的宽度为 NN 米，小鸟每飞行 LL 米就必须在一片荷叶上休息一下，才能够继续飞行。当然，小鸟们也可以选择没飞够 LL 米就先休息一下，但不能一次飞超过 LL 米。 距离小鸟们出发的河岸一侧距离为 ii 的荷叶共有 AiA_i 片，每片荷叶在有小鸟停于上方休息后， 就会沉入水底，不能够再供其他小鸟休息。

现在想要知道，至多有多少只小鸟能够抵达对岸。

输入格式

第一行输入两个整数 N,LN,L，含义见题面描述。 接下来一行 N−1N-1 个整数 AiA_i，表示距离河的出发一侧距离为 ii 的荷叶的片数。

输出

输出一行一个整数，表示至多能够抵达前线的小鸟数量。

输入输出样例

样例输入 #1

1
2
10 5
0 0 1 0 2 0 0 1 0

样例输出 #1

1
3

样例解释 #1

三只小鸟可以分别走 0→5→10;0→5→10;0→3→8→100→5→10;0→5→10;0→3→8→10。

样例输入 #2

1
2
10 3
1 1 1 1 2 1 1 1 1

样例输出 #2

1
3

样例解释 #2

三只小鸟可以分别走 0→1→4→7→10;0→2→5→8→10;0→3→6→9→100→1→4→7→10;0→2→5→8→10;0→3→6→9→10。

数据范围

对于 20%20\%的数据，L=N−1L=N-1。
对于 50%50\%的数据，1≤L<N≤5,0≤Ai≤31≤L<N≤5,0≤Ai≤3。
对于 80%80\%的数据，1≤L<N≤100,0≤Ai≤101≤L<N≤100,0≤Ai≤10。
对于 100%100\%的数据，1≤L<N≤105,0≤Ai≤1041≤L<N≤10^5,0≤Ai≤10^4。

题解

思路

70Pts做法：

我们看到最大问题而且还有上界限制时，很容就就能想到网络流。

我们可以将每个有值的点和这个点能到达的有值的点连边，边的上界可以设置为去往的点的权值，最后几个可以直接到达的点可以合并为一个“超级汇点”，然后跑最大流就可以了。

因为最大流的时间复杂度以及建图会RE，所以只能过前7个点，小常数选手可能可以跑到80Pts。

代码实现

时间复杂度O(n2m)O(n^2m)

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
82
83
84
85
86
87
88
#include<iostream>
#include<array>
#include<algorithm>
#include<cmath>
#include<bitset>
using namespace std;
using gg=long long;
array<gg,10010> nxt,to,cap,flow;
array<gg,110> a,head;
bitset<110> alr;
const gg homo=114514114514;
gg cnt=1,n;
void add(const gg &fr,const gg &t,const gg &v)
{
	cnt++;
	nxt[cnt]=head[fr];
	to[cnt]=t;
	cap[cnt]=v;
	head[fr]=cnt;
	return;
}
gg dfs(const gg &p,const gg &v)
{
	if(v==0||p==n) return v;
	alr[p]=true;
	for(gg i=head[p];i;i=nxt[i])
	{
		if(alr[to[i]]) continue;
		gg re=dfs(to[i],min(v,cap[i]-flow[i]));
		if(re)
		{
			flow[i]+=re;
			flow[i^1]-=re;
			return re;
		}
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	//freopen("river.in","r",stdin);
	//freopen("river.out","w",stdout);
	gg l;
	cin>>n>>l;
	for(gg i=1;i<n;i++)
	{
		cin>>a[i];
	}
	for(gg i=1;i<=l;i++)
	{
		if(a[i])
		{
			add(0,i,a[i]);
			add(i,0,0);
		}
	}
	for(gg i=1;i<n;i++)
	{
		if(!a[i]) continue;
		for(gg j=i+1;j<n&&j-i<=l;j++)
		{
			if(!a[j]) continue;
			add(i,j,a[j]);
		    add(j,i,0);
		}
	}
	for(gg i=n-l;i<n;i++)
	{
		if(a[i])
		{
			add(i,n,a[i]);
			add(n,i,0);
		}
	}
	gg ans=0; 
	while(1)
	{
		for(gg i=0;i<=n;i++) alr[i]=false;
		gg f=dfs(0,homo);
		if(!f) break;
		ans+=f;
	}
	cout<<ans<<'\n';
	return 0;
}

100Pts做法：

我们可以考虑贪心，对于每次操作，显然跳的时候要尽可能的使跳的距离最长，这样的话选择就会更多，所以我们只需要两遍遍历即可解决问题

代码实现

时间复杂度O(n)O(n)

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<iostream>
#include<array>
#include<algorithm>
#include<cmath>
#include<bitset>
using namespace std;
using gg=long long;
array<gg,100010> a;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	gg ans=114514114514114514,n,l;
	cin>>n>>l;
	for(gg i=1;i<n;i++)
	{
		cin>>a[i];
		a[i]+=a[i-1];
	}
	for(gg i=l;i<n;i++)
	{
		ans=min(ans,a[i]-a[i-l]);
	}
	cout<<ans<<'\n';
	return 0;
}

总结

考试的时候先想到了贪心+二分，想了一会不太会实现这个贪心，而且感觉策略似乎不对，就没硬写，光写了个最大流，没想到还能拿到70分awa。

FiresonZOier

一名高中蒟蒻Oier