牛客多校第六场

D Move

题意

要把n个物品放到k个盒子里,每个物品都有一个体积,每次找与这个盒子最接近的体积放进去,直到放不下,然后去放下一个盒子直到放完,求盒子最小的体积.

思路

显然这个题每个不能二分体积,然后暴力找体积范围为[ceil(sum/k),ceil(sum/k)+maxV]

,sum是所有物品的总体积,maxV是最大的体积,对于每个体积在按题意模拟即可.

代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int a[maxn];
int n,m,k;
bool check(int mid){
multiset<int> s;
for (int i = 1; i <= n; i++)
s.insert(a[i]);
for (int i = 1; i <= k; i++){
int lst=mid;
auto it=s.upper_bound(lst);
while(it!=s.begin()){
lst-=*(--it);
s.erase(it);
it=s.upper_bound(lst);
}
}
if (s.empty()) return true;
return false;
}
int main(){
int _;
while(~scanf("%d",&_)){
int id=0;
while(_--){
scanf("%d%d",&n,&m);
int maxx=0;
int sum=0;
k=m;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
maxx=max(a[i],maxx);
sum+=a[i];
}
int ans=ceil(1.0*sum/m);
for(int i=ceil(1.0*sum/m);i<=ceil(sum/m)+maxx;i++){
if(check(i)) {
ans=i;
break;
}
}
printf("Case #%d: %d\n",++id,ans);
}
}
}

J Upgrading Technology

题意

有i个技术初始为0级,可升最高等级为j级,第i个技术j-1级时升一级消费$c_{ij}$当所有物品升到同一级时会有$d_j$的利润,问最大的利润是多少.

思路

记录后缀最小然后依次比较就行了.

思路

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 10;
ll a[maxn][maxn];
ll b[maxn][maxn];
ll d[maxn];
int main(){
int _;
while (~scanf("%d", &_)){
int id = 0;
while (_--){
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++){
a[i][0]=0;
for (int j = 1; j <= m; j++){
scanf("%lld", &a[i][j]);
a[i][j] += a[i][j - 1];
b[i][j] = a[i][j];
}
}
for (int i = n; i >= 1; i--){
for (int j = m - 1; j >= 0; j--){
a[i][j] = min(a[i][j], a[i][j + 1]);
}
}
for (int i = 1; i <= m; i++){
scanf("%lld", &d[i]);
d[i] += d[i - 1];
}
ll ans = 0;
for (int i = 0; i <= m; i++){
ll anss = 0;
for (int j = 1; j <= n; j++){
anss += a[j][i];
}
ll an = 1e18;
for (int j = 1; j <= n; j++){
an = min(an, anss - a[j][i] + b[j][i]);
}
ans = max(ans, d[i] - an);
}
printf("Case #%d: %lld\n", ++id, ans);
}
}

//system("pause");
}