NOIP2018普及组第三题解析

题目链接:

https://www.luogu.com.cn/problem/P5017

这题难度飙升。。。

10分:

//10
#include <bits/stdc++.h>
using namespace std;
int main()
{
	//freopen ("bus.in","r",stdin);
	//freopen ("bus.out","w",stdout);
	int n,m;
	int a;
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		cin>>a;
	}
	cout<<"0";
	//fclose (stdin); fclose (stdout);
	return 0;
} 

↑骗分。

分析:

本题做法:动态规划!(DP)

首先将t数组升序排序

设f[i][j]表示第i个人等了j分钟的车,载完前i个人的最小等车时间总和。

j的取值范围?

由题可知,若车在人大附中停了m分钟,那么不如在到人大附中时先送走一批人(即便当时没人),所以停车时间T1<m

设一个人等到车从人民大学回来的时间为T2
因为车往返一次只需m分钟,所以T2<m

综上,一个人等车的时间

j=T1+T2<2m

该如何转移?

  1. 若下一个人能赶上当次车(即t[i]+j>=t[i+1]), 则将f[i][j]+t[i]+j-t[i+1]转移至f[i+1][t[i]+j-t[i+1]];
  2. 若下一个人在当次车回来之前开始等车(即t[i]+j+m>=t[i+1]), 则枚举车回来后停的时间k, 用f[i][j]+t[i]+j+m+k-t[i+1]转移f[i+1][t[i]+j+m+k-t[i+1]];
  3. 若下一个人在当次车回来之后才到(即t[i]+j+m<t[i+1]),则枚举下 一个人等待的时间k,并用f[i][j]+k转移f[i+1][k];

空间复杂度O(nm),时间复杂度O(nm^2)。

50 分的做法,时间复杂度为 O(t^2)。代码如下:

#include <cstdio>
#include <algorithm>
const int maxT = 4000105;
int n, m, t, ti, ans = 1e9, cnt[maxT], sum[maxT], f[maxT];
int main() 
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) 
    {
        scanf("%d", &ti); t = std::max(t, ti);
        cnt[ti]++; sum[ti] += ti;
    }
    for (int i = 1; i < t + m; i++) { cnt[i] += cnt[i - 1]; sum[i] += sum[i - 1]; } // 前缀和.
    for (int i = 0; i < t + m; i++) 
    {
        f[i] = cnt[i] * i - sum[i]; // 特判边界情况.
        for (int j = 0; j <= i - m; j++) { f[i] = std::min(f[i], f[j] + (cnt[i] - cnt[j]) * i - (sum[i] - sum[j])); }
    }
    for (int i = t; i < t + m; i++) { ans = std::min(ans, f[i]); }
    printf("%d\n", ans);
    return 0;
}

时间复杂度降至 O(tm),可得 70 ~ 100不等的成绩

代码如下:

#include <cstdio>
#include <algorithm>
const int maxT = 4000105;
int n, m, t, ti, ans = 1e9, cnt[maxT], sum[maxT], f[maxT];
int main() 
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) 
    {
        scanf("%d", &ti); t = std::max(t, ti);
        cnt[ti]++; sum[ti] += ti;
    }
    for (int i = 1; i < t + m; i++) { cnt[i] += cnt[i - 1]; sum[i] += sum[i - 1]; } // 前缀和.
    for (int i = 1; i < t + m; i++) {
        f[i] = cnt[i] * i - sum[i]; // 特判边界情况.
        for (int j = std::max(i - m - m + 1, 0)/*剪去无用转移*/; j <= i - m; j++) { f[i] = std::min(f[i], f[j] + (cnt[i] - cnt[j]) * i - (sum[i] - sum[j])); }
    }
    for (int i = t; i < t + m; i++) { ans = std::min(ans, f[i]); }
    printf("%d\n", ans);
    return 0;
}

易知,随着 j的增大,能够转移的 k 的上限也不断增大,故使用前缀最小值维护可以转移的 gi−1, k

时间复杂度为 O(n log n+nm),即 O(nm),目前看应该是最快的 dp做法了。注意边界细节,AC代码如下:

#include <cstdio>
#include <algorithm>

const int maxN = 505, maxM = 205;

int n, m, mm, ans = 1e9, t[maxN], g[maxN][maxM];

int main() {
    scanf("%d%d", &n, &m); mm = m + m;
    for (int i = 1; i <= n; i++) { scanf("%d", &t[i]); }
    std::sort(t + 1, t + n + 1); // 排序. 
    for (int i = 1; i <= n; i++) {
    	g[i][0] = 1e9; // 先特判 j = 0 的情况. 
    	for (int j = 0; j <= std::min(t[i] - t[i - 1] - m, m - 1); j++) { g[i][0] = std::min(g[i][0], g[i - 1][j]); }
    	for (int j = 1; j < mm; j++) { g[i][j] = std::min(g[i][j - 1], t[i] + j - t[i - 1] - m >= 0 && t[i] + j - t[i - 1] - m < mm ? g[i - 1][t[i] + j - t[i - 1] - m] : (int) 1e9); } // 前缀最大值维护新开一段的情况. 
    	for (int j = 0; j < mm; j++) { g[i][j] = std::min(g[i][j], t[i] + j - t[i - 1] < mm ? g[i - 1][t[i] + j - t[i - 1]] : (int) 1e9) + j; } // 分在同一段内的情况, 加上 j 的贡献. 
    }
    for (int i = 0; i < m; i++) { ans = std::min(ans, g[n][i]); }
    printf("%d\n", ans);
    return 0;
}

注:本人在做的时候只得了50分。所以AC代码由洛谷用户https://www.luogu.com.cn/user/26673提供。

完结!!

0 0 vote
Article Rating
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x