2017 C语言积分赛 周赛一 A题 我们fgo玩家是这样的 题解
题目描述
小辉最近沉迷于玩手机游戏，不仅玩，而且他还同时玩很多个。然而在元旦一天，所有的手机游戏在那一阵都有活动。而且由于他玩的游戏比较多，所有一共可能有几万个活动【你就不能少玩一点手游吗(╯°□°）╯︵ ┻━┻】 因为活动时间有重叠，他不能同时打2个活动，也不能中途放弃活动。所以他把自己所有的活动都列了出来，每个活动的起始时间和终止时间做成纯整数字的形式【所以说为什么是纯数字啊(╯°□°）╯︵ ┻━┻】，请聪明的同学们帮忙看看小辉至少会错过多少个活动
输入
1、 活动终止时间永远大于该活动的起始时间。所有活动用”[”和”]”包起来，并且整合在一个”[“和”]”中，活动之间也用逗号隔开，如：[[0,6,],[10,12]]。 2、 像[5,6]和[6,7]这样的2个活动，虽然时间接在一起，但是不会互相重叠。 3、 所有数据不大于2147483647 (int的最大范围)
4.活动最多10，000个
输出
输出小序至少会错过的活动数目
样例输入
|
1 |
[[1,2],[2,3],[1,2],[3,4],[1,3]] |
样例输出
|
1 |
2 |
可贪心可DP，这里介绍DP写法。
思路：
1、先按结束时间排序，再在相同的结束时间区间内按开始时间排序。
2、因为此时已经严格有序，所以每次寻找结束时间离当前活动开始时间最近的活动。
状态转移方程：f[t[i]]=maxn(f[t[i-1]],f[t[temp]]+1);
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 |
#include<stdio.h> #include<string.h> #define maxn(a,b) ((a)>(b))?(a):(b) int n=1,a[1000010],b[1000010],t[1000010],f[1000010]; void kuai(int l,int r) { int i=l,j=r,mid=b[t[(l+r)>>1]]; while(i<=j) { while(b[t[i]]<mid) i++; while(b[t[j]]>mid) j--; if(i<=j) { int tmp=t[i]; t[i]=t[j]; t[j]=tmp; i++; j--; } } if(l<j) kuai(l,j); if(r>i) kuai(i,r); } void kuai1(int l,int r) { int i=l,j=r,mid=a[t[(l+r)>>1]]; while(i<=j) { while(a[t[i]]<mid) i++; while(a[t[j]]>mid) j--; if(i<=j) { int tmp=t[i]; t[i]=t[j]; t[j]=tmp; i++; j--; } } if(l<j) kuai(l,j); if(r>i) kuai(i,r); } int main() { getchar(); while(scanf("[%d,%d]",&a[n],&b[n])!=EOF) { t[n]=n; getchar(); n++; } n--; int i,temp=0; kuai(1,n); for(i=1;i<=n;i++) { int tmp=b[t[i]],j=i; while(tmp==b[t[j+1]]) j++; kuai1(i,j); } for(i=1;i<=n;i++) { while(b[t[temp+1]]<=a[t[i]]) temp++; f[t[i]]=maxn(f[t[i-1]],f[t[temp]]+1); } printf("%d",n-f[t[n]]); return 0; } |