牛客小白月赛2

https://www.nowcoder.com/acm/contest/86#question

所有代码：

https://pan.baidu.com/s/1B0a4CZ6HFev0iwDdtDwBcA

传说中的随机化方法找答案，直到找到答案

适合于成功率不少的方法

类似：

一个区域内撒点

几何题

避免k=0和k=无穷

如Codeblocks，

Ctrl+R , 变为 “,”

正常：dfs

idea：

如果n过大，用dfs可能超时(保存函数状态)，可以使用bfs。

一轮bfs，从根节点出发，获得边的父亲、节点关系。

一轮bfs，从叶子节点出发，数组存储节点的状态(子节点反馈信息给父节点)。

注意father[root]=0（有多组数据）

注意愉悦度小于0的时候不选。

Way1

以一个时间开始，到下一个时间，最多只有两个节目(分别在两个舞台)

i,j两变量递增，代表两个舞台

容易写错

写之前理清思路

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <time.h>
 6 #include <string>
 7 #include <set>
 8 #include <map>
 9 #include <list>
10 #include <stack>
11 #include <queue>
12 #include <vector>
13 #include <bitset>
14 #include <ext/rope>
15 #include <algorithm>
16 #include <iostream>
17 using namespace std;
18 #define ll long long
19 #define minv 1e-6
20 #define inf 1e9
21 #define pi 3.1415926536
22 #define E  2.7182818284
23 const ll mod=1e9+7;//998244353
24 const int maxn=1e5+10;
25 
26 struct node
27 {
28     int x,v;
29 }p[maxn],q[maxn];
30 
31 int cmp(node a,node b)
32 {
33     return a.x<b.x;
34 }
35 
36 int main()
37 {
38     int n,m,T,i,j,pos,t,v;
39     ll sum=0;
40     scanf("%d%d%d",&n,&m,&T);
41     for (i=1;i<=n;i++)
42         scanf("%d%d",&p[i].x,&p[i].v);
43     for (i=1;i<=m;i++)
44         scanf("%d%d",&q[i].x,&q[i].v);
45     sort(p+1,p+n+1,cmp);
46     sort(q+1,q+m+1,cmp);
47 
48     i=1,j=1;pos=0;
49     p[n+1].x=q[m+1].x=T;
50     while (i<=n && j<=m)
51     {
52         t=min(p[i+1].x,q[j+1].x);
53         v=max(p[i].v,q[j].v);
54         if (t>=T)
55         {
56             if (v>0)
57                 sum+=1ll*v*(T-pos);
58             break;
59         }
60         if (v>0)
61             sum+=1ll*v*(t-pos);
62         pos=t;
63         if (p[i+1].x<q[j+1].x)
64             i++;
65         else if (p[i+1].x>q[j+1].x)
66             j++;
67         else
68             i++,j++;
69     }
70     cout<<sum;
71     return 0;
72 }
73 /*
74 1 2 5
75 0 3
76 0 1
77 2 5
78 21
79 
80 1 3 5
81 0 3
82 0 1
83 2 5
84 3 1
85 17
86 
87 1 1 1000000000
88 0 100
89 0 100
90 */

Way2

舞台切换没有代价，所以认为算同一时间内最优的即可

使用排序+离散化

对于一个舞台，所有节目的和小于等于总体（O(n)）

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <time.h>
  6 #include <string>
  7 #include <set>
  8 #include <map>
  9 #include <list>
 10 #include <stack>
 11 #include <queue>
 12 #include <vector>
 13 #include <bitset>
 14 #include <ext/rope>
 15 #include <algorithm>
 16 #include <iostream>
 17 using namespace std;
 18 #define ll long long
 19 #define minv 1e-6
 20 #define inf 1e9
 21 #define pi 3.1415926536
 22 #define E  2.7182818284
 23 const ll mod=1e9+7;//998244353
 24 const int maxn=2e5+10;
 25 
 26 struct node
 27 {
 28     int x,v;
 29 }p[maxn],q[maxn];
 30 int a[maxn],v[maxn],t[maxn];
 31 
 32 int cmp(node a,node b)
 33 {
 34     return a.x<b.x;
 35 }
 36 
 37 int main()
 38 {
 39     int n,m,T,i,j,k,g=0;
 40     ll sum=0;
 41     scanf("%d%d%d",&n,&m,&T);
 42 
 43     for (i=1;i<=n;i++)
 44         scanf("%d%d",&p[i].x,&p[i].v);
 45     sort(p+1,p+n+1,cmp);
 46 
 47     for (i=1;i<=m;i++)
 48         scanf("%d%d",&q[i].x,&q[i].v);
 49     sort(q+1,q+m+1,cmp);
 50 
 51     for (i=1;i<=n;i++)
 52         t[++g]=p[i].x;
 53     for (i=1;i<=m;i++)
 54         t[++g]=q[i].x;
 55     t[++g]=T;
 56     sort(t+1,t+g+1);
 57 
 58     j=0;
 59     t[0]=-1;
 60     for (i=1;i<=g;i++)
 61         if (t[i]!=t[i-1])
 62             a[++j]=t[i];
 63 
 64     for (i=2;i<=g;i++)
 65         v[k]=-inf;
 66     p[n+1].x=max(p[n].x,T);
 67     j=1;
 68     for (i=1;i<=n;i++)
 69     {
 70         while (a[j]!=p[i].x)
 71             j++;
 72         k=j;
 73         while (a[k]!=p[i+1].x)
 74         {
 75             k++;
 76             v[k]=max(v[k],p[i].v);
 77         }
 78     }
 79 
 80     q[m+1].x=max(q[m].x,T);
 81     j=1;
 82     for (i=1;i<=m;i++)
 83     {
 84         while (a[j]!=q[i].x)
 85             j++;
 86         k=j;
 87         while (a[k]!=q[i+1].x)
 88         {
 89             k++;
 90             v[k]=max(v[k],q[i].v);
 91         }
 92     }
 93 
 94     for (i=2;i<=g;i++)
 95     {
 96         if (a[i]>=T)
 97         {
 98             if (v[i]>0)
 99                 sum+=1ll*v[i]*(T-a[i-1]);
100             break;
101         }
102         if (v>0)
103             sum+=1ll*v[i]*(a[i]-a[i-1]);
104     }
105     cout<<sum;
106     return 0;
107 }
108 /*
109 1 2 5
110 0 3
111 0 1
112 2 5
113 25
114 */