C

模拟
有n台服务器,每台负载为$m_i$,要求重新分配负载,即可将一个单位的负载移到另一台服务器上,每次消耗1s
求使得$m_{max} - m_{min}$最小的最小消耗

我们易知最终每台服务器负载为sum/n (+1)
排序后我们得出其与原来差的和即可

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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int m[maxn];

int main()
{
//freopen("test.txt","r",stdin);
int n;
scanf("%d",&n);
int sum = 0;
for(int i=0;i<n;++i) scanf("%d",m+i),sum += m[i];
sort(m,m+n,greater<int>());
int ans = 0;
int cur = sum/n,rem = sum%n;
for(int i=0;i<n;++i)
{
if(i+1 <= rem)
ans += abs(m[i]-cur-1);
else
ans += abs(m[i]-cur);
}
// printf("%d\n",ans);
printf("%d\n",ans/2);
return 0;
}

D

二分答案
一个人持有s burles,有n天,每天有对应dollar和pound的汇率,总共有m个零件,对应有两种类型,类型1只能用美元购买,类型2只能用英镑购买,每天可以购买多个零件。求最小的d,使得d天内可以买k个零件,并输出购买零件的编号和第几天购买。

题目有点难读。。。不过读懂了就好理解了。
我们发现某种类型一定是在汇率较低的某一天全部买完的,我们若在第x天可以买完,则第x+1天也可以买完,因此我们分别预处理出当天之前对应两种货币的最小的汇率,二分天数,判断当天之前能否买完

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
89
90
91
92
93
94
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 2e5 + 10;
int n,m,k,s,ci,cj;
int a[maxn],b[maxn],ma[maxn],mb[maxn];
vector<LL> gad[2];
vector<pair<int,int> > id[2];

bool yes(int m)
{
for(int i=0;i<=k;++i)
{
int j = k-i;
if(i<gad[0].size() && j<gad[1].size() && gad[0][i]*ma[m] + gad[1][j]*mb[m] <= s)
{
ci = i, cj = j;
return 1;
}
}
return 0;
}

int solve()
{
int L = 0,R = n-1,res = -1;
while(L<=R)
{
int m = (L+R)/2;
if(yes(m))
{
res = m;
R = m-1;
}
else L = m+1;
}
return res+1;
}


int main()
{
//freopen("test.txt","r",stdin);
scanf("%d %d %d %d",&n,&m,&k,&s);
for(int i=0;i<n;++i) scanf("%d",a+i);
for(int i=0;i<n;++i) scanf("%d",b+i);
int mna = a[0], mnb = b[0];
for(int i=0;i<n;++i)
{
mna = min(mna,a[i]);
mnb = min(mnb,b[i]);
ma[i] = mna; mb[i] = mnb;
}
for(int i=0;i<m;++i)
{
int t,c;
scanf("%d %d",&t,&c);
gad[t-1].push_back(c);
id[t-1].push_back(make_pair(c,i+1));
}
for(int z=0;z<2;++z)
{
gad[z].push_back(0);
sort(gad[z].begin(),gad[z].end());
sort(id[z].begin(),id[z].end());
for(int i=1;i<gad[z].size();++i) gad[z][i] += gad[z][i-1];
}
int res = solve();
if(!res) puts("-1");
else
{
printf("%d\n",res);
int ca,cb; ca = cb = -1;
for(int i=0;i<n;++i)
{
if(ma[i] == ma[res-1])
{
ca = i+1;
break;
}
if(mb[i] == mb[res-1])
{
cb = i+1;
break;
}
}
if(ca == -1) ca = res;
else cb = res;
for(int i=0;i<ci;++i) printf("%d %d\n",id[0][i].second,ca);
for(int i=0;i<cj;++i) printf("%d %d\n",id[1][i].second,cb);
}
return 0;
}

E

最小生成树+LCA
求包含某条边的最小生成树

先求最小生成树,然后若包含的这条边在生成树上直接输出,否则我们加入这条边,删除这条边形成的环上的第二大的边,可以通过LCA来处理。

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 2e5 + 10;

int n,m;
struct Edge{
int u,v,w,id;
Edge(int u,int v,int w,int id):u(u),v(v),w(w),id(id) {}
bool operator<(const Edge& rhs) const{
return w < rhs.w;
}
};

vector<int> G[maxn];
vector<Edge> edges;
int f[maxn],ans[maxn];

int find(int x)
{
return f[x] ? f[x] = find(f[x]):x;
}

LL Kruskal()
{
LL res = 0;
sort(edges.begin(),edges.end());
for(int i=0;i<edges.size();++i)
{
int u = find(edges[i].u),v = find(edges[i].v);
if(u != v)
{
f[u] = v;
res += edges[i].w;
ans[edges[i].id] = 0;
G[edges[i].u].push_back(i);
G[edges[i].v].push_back(i);
//printf("%d %d\n",edges[i].u,edges[i].v);
}
}
return res;
}

const int LOG = 18;
int p[maxn][LOG],deep[maxn],mx[maxn][LOG];

void dfs(int u,int fa,int dep = 1)
{
//printf("%d %d\n",u,fa);

p[u][0] = fa;
deep[u] = dep;

for(int i=1;i<LOG;++i)
if(p[u][i-1] != -1)
p[u][i] = p[p[u][i-1]][i-1];

for(int i=0;i<G[u].size();++i)
{
int v = edges[G[u][i]].v;
if(v == u) v = edges[G[u][i]].u;
if(fa == v) continue;
mx[v][0] = edges[G[u][i]].w;
dfs(v,u,dep+1);
}
}

int query(int u,int v)
{
if(deep[u] < deep[v] ) swap(u,v);
int resu = mx[u][0],resv = mx[v][0];

for(int i = LOG-1;i>=0;--i)
{
if(p[u][i] != -1 && deep[p[u][i]] >= deep[v])
{
resu = max(resu,mx[u][i]);
u = p[u][i];
}
}

if(u == v) return resu;

for(int i = LOG-1;i>=0;--i)
{
if(p[u][i] != p[v][i])
{
resu = max(resu,mx[u][i]);
u = p[u][i];
resv = max(resv,mx[v][i]);
v = p[v][i];
}
}
resu = max(resu,mx[u][0]);
resv = max(resv,mx[v][0]);
return max(resu,resv);
}

void init()
{
memset(f,0,sizeof f);
memset(p,-1,sizeof p);
memset(ans,-1,sizeof ans);
memset(mx,0,sizeof mx);
}

int main()
{
//freopen("test.txt","r",stdin);
init();
int n,m;
scanf("%d %d",&n,&m);
for(int i=0;i<m;++i)
{
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
edges.push_back(Edge(u,v,w,i));
}
LL res = Kruskal();
dfs(1,-1);

for(int i=1;i<LOG;++i)
{
for(int j=1;j<=n;++j)
{
if(p[j][i-1] != -1)
{
mx[j][i] = max(mx[j][i-1],mx[p[j][i-1]][i-1]);
}
}
}

for(int i=0;i<edges.size();++i)
{
if(ans[edges[i].id])
{
int d = query(edges[i].u,edges[i].v);
// printf("%d %d \n",edges[i].id,d);
ans[edges[i].id] = edges[i].w - d;
}
}

for(int i=0;i<m;++i) printf("%lld\n",res + ans[i]);
return 0;
}