基本情况:
A和B直接秒了,C题没写出来大致是思路的问题,下面就讲一下C自己的思路和题解
C - Leftover Recipes
题目概述,先输入一个数字代表有多少中配料,然后依次输入A菜每种配料所需的量,然后输入B菜每种配料所需的量,最后输出最多可以做多少盘菜
样例: 2
800 300
100 100
200 10 输出为5
自己的想法:看到这个的时候先在草稿纸上假设A菜做x盘,B菜做y盘,然后就列了两个不等式100x+200y<=800和100x+10y<=300然后根据这两个不等式来判断x+y的最大值,一开始以为可以用高中的数学判断极值的方法拉格朗日数乘,但是后面发现给的条件是带有不等号的貌似不能用,因为拉格朗日数乘需要的是等号条件之后再分别求导(可能后面比赛会用到这个)。发现不行后想线性规划,之后就想直接算出每当个不等式取等号的时候于x轴的交点,然后依次判断获取最小的与x轴交点的值。然后通过for循环依次判断当x=0到那个交点范围内所有整数x的值,最后把x值代入不等式获取y(这个过程需要带到每个不等式然后获取最小的y),之后x和y相加再判断最大值
题解:先固定一边(x或y)之后再循环判断每个x值时y的取值,后再判断哪个时候最大,当然x固定后,也要固定y。确保所有情况都考虑到(感觉其实和自己的挺像的,但自己的思路是通过找到最大值x来循环y,其实这样循环次数反而增加了,倒不如就像题解一样,把所有x值都取然后判断y)
`#include <bits/stdc++.h>
using namespace std;
const int inf =INT_MAX,N=20;
int n,i,e1,e2,x,y,ans,flag,q[N],a[N],b[N],f[N];
int main(){
cin>>n;e1=e2=inf;ans=-inf;y=inf;flag=0;
for( i=1;i<=n;i++){
cin>>q[i];
}
for(i =1;i<=n;i++){
cin>>a[i];
if(a[i]>0)e1=min(e1,q[i]/a[i]);
}
for(i =1;i<=n;i++){
cin>>b[i];
if(b[i]>0)e2=min(e2,q[i]/b[i]);
}
for(x=0;x<=e1;x++){
if(flag)break;
for(i=1;i<=n;i++)f[i]=q[i]-a[i]x;
for(i=1;i<=n;i++){
if(f[i]<0){flag=1;break;}
if(b[i]<0){y=min(y,f[i]/b[i]);}
}
ans =max(ans,x+y);
}
flag=0;
for(y=0;y<=e2;y++){
if(flag)break;
for(i=1;i<=n;i++)f[i]=q[i]-a[i]y;
for(i=1;i<=n;i++){
if(f[i]<0){flag=1;break;}
if(a[i]<0){x=min(x,f[i]/a[i]);}
}
ans =max(ans,x+y);
}
cout<<ans;
}`
有二分做法,过一会学了补充
标签:AtCoder,338,Beginner,cin,flag,ans,inf,e1,e2 From: https://www.cnblogs.com/sixsix666/p/17992426