UVa 10163 Storage Keepers

题目

◇题目传送门◆（由于UVa太慢，这里提供一个vjudge的链接）
◇题目传送门（vjudge）◆

题目大意

有$N$个相同的仓库需要一些看守。现有$M$个管理员来应聘，第$i$个人的能力值为$p_i$，所需工资也是$p_i$。若将第$i$个人派去看守$k$个仓库，则每个仓库的安全系数为$\lfloor\frac{p_i}{k}\rfloor$；没有人看守的仓库安全系数为$0$。求在最小安全系数最大的情况下，最少需要支付的工资总和。

思路

最大化最小值，很明显具有二分的性质。

所以我们用二分求出最小安全系数，再求工资总和。

工资总和最小，这个问题我们可以使用DP解决。

定义$f[j]$前$j$个仓库所需的最少工资总和，不难列出状态转移方程：

其中$1\le i\le M,1\le j\le N,1\le k\le j$。

综上，我们在二分的时候使用DP判断并维护最小值。注意：当$p[i]/k$小于当前最小安全系数的时候退出循环。

正解代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;const int Maxn=100;
const int Maxm=30;
const int INF=0x3f3f3f3f;int N,M,p[Maxm+5];
int f[Maxn+5];
int ans,sum;bool Check(int x) {memset(f,0x3f,sizeof f);f[0]=0;for(int i=1;i<=M;i++)for(int j=N;j>=1;j--)for(int k=1;k<=j;k++) {
   //k为第i个人所需看守的仓库数量if(p[i]/k<x)//当安全系数小于x（当前最小安全系数）时不能转移break;f[j]=min(f[j],f[j-k]+p[i]);}if(f[N]>=INF)return false;sum=f[N];//记录当前最小工资总和return true;
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifwhile(scanf("%d %d",&N,&M)!=EOF&&N&&M) {sum=ans=0;for(int i=1;i<=M;i++)scanf("%d",&p[i]);int lb=0,ub=1000;while(lb+1<ub) {int mid=lb+(ub-lb)/2;if(Check(mid))ans=mid,lb=mid;else ub=mid;}printf("%d %d\n",ans,sum);}return 0;
}