Codeforces Round #667 (Div. 3) 参与排名人数12482
[codeforces 1409B] Minimum Product 让两数的差距越大越好
总目录详见https://blog.csdn.net/mrcrack/article/details/103564004
在线测评地址http://codeforces.com/contest/1409/problem/B
题目大意:给出a,b两个数,每次可以让a或b减小1,减小后的a不能小于x,b不能小于y,总次数不能超过n,多次处理后,要求a*b的结果最小,输出这个最小值。
基本思路:让两数的差距越大越好。
样例模拟如下:
10 10 8 5 3
70
(1)10-8=2,3-2=1,10-1=9,(10-2)*(10-1)=72
(2)10-5=5,min(5,3)=3,3-3=0,(10-0)*(10-3)=70
取最小值70
12 8 8 7 2
(1)12-8=4,min(4,2)=2,2-2=0,(12-2)*(8-0)=80
(2)8-7=1,2-1=1,12-1=11,(12-1)*(8-1)=77
取最小值77
10 11 2 1 5
(1)10-2=8,min(8,5)=5,5-5=0,(10-5)*(11-0)=55
(2)11-1=10,min(10,5)=5,5-5=0,(10-0)*(11-5)=60
取最小值55
10 11 9 1 10
(1)10-9=1,10-1=9,(10-1)*(11-9)=18
(2)11-1=10,10-10=0,(10-0)*(11-10)=10
取最小值10
AC代码如下:
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
int main(){
int t;
LL a,b,x,y,n,c,d,ans,m;
scanf("%d",&t);
while(t--){
scanf("%lld%lld%lld%lld%lld",&a,&b,&x,&y,&n);
m=n;//情况1,尽量减小a
c=min(a-x,m);
m-=c;
d=min(b-y,m);
ans=(a-c)*(b-d);
m=n;情况2,尽量减小b
d=min(b-y,m);
m-=d;
c=min(a-x,m);
ans=min((a-c)*(b-d),ans);
printf("%lld\n",ans);
}
return 0;
}