洛谷P2514

bzoj2426

其实是个简单的贪心,然而不适合在脑子不清醒的时候做...看不懂题意续了1个小时

很容易发现应该枚举新建哪个发电厂,对于这种方案就是取其中b吨煤运到原来发电厂,取剩下(suma-b)吨煤运到新发电厂。首先假设全部都运到原来发电厂,然后把其中suma-b吨代价最小的改为运到新发电厂即可

 #include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
ll m,b,n;
ll h[];
ll a[],c[],d[],e[];
ll s1,s2,s3,s;
ll ansx,ansy=0x3f3f3f3f3f3f3f3f;
bool c1(ll x,ll y)
{
return d[x]-c[x]<d[y]-c[y];
}
int main()
{
ll i,j,t;
scanf("%lld%lld%lld%lld",&m,&b,&h[],&n);
for(i=;i<=m;++i)
{
scanf("%lld",&a[i]);
s+=a[i];
}
s-=b;
for(i=;i<=n;++i)
scanf("%lld",&h[i]);
for(i=;i<=m;++i)
{
scanf("%lld",&c[i]);
s1+=a[i]*c[i];
}
for(i=;i<=n;++i)
{
for(j=;j<=m;++j)
scanf("%lld",&d[j]);
for(j=;j<=m;++j)
e[j]=j;
sort(e+,e+m+,c1);
s2=s1;s3=;
for(j=;j<=m;++j)
{
t=min(a[e[j]],s-s3);
s2+=t*(d[e[j]]-c[e[j]]);
s3+=t;
}
s2+=h[];s2+=h[i];
if(s2<ansy) {ansy=s2;ansx=i;}
}
printf("%lld\n%lld\n",ansx,ansy);
return ;
}
05-08 08:21