S2OJ-1470饥饿的小鸟(river)题解

题面

题目描述

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

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

输入格式

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

输出

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

输入输出样例

样例输入 #1

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

样例输出 #1

1
3

样例解释 #1

三只小鸟可以分别走 0510;0510;038100→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

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

数据范围

对于 20%20\%的数据,L=N1L=N-1
对于 50%50\%的数据,1L<N5,0Ai31≤L<N≤5,0≤Ai≤3
对于 80%80\%的数据,1L<N100,0Ai101≤L<N≤100,0≤Ai≤10
对于 100%100\%的数据,1L<N105,0Ai1041≤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。