gym100553

B 贪心 结构体排序
怒气值<=B 开心值>=A
按照性价比排序 bi不变si尽量大 使总量更接近B
si尽量大 si
ai也就越大 总开心值一定越大
int 除0异常 RE 保留10-8以上精度
gym100553

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
#define IO ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb emplace_back
#define pii pair<int,int>
#define all(n) (n).begin(),(n).end()
#define rep(i,a,n) for (int i=a;i<=n;i++)

const int maxn = 1e5+5;
const ll mod = 1e9+7;
const int inf = 0x3f3f3f3f;
ll gcd(ll a,ll b)
{
	return b!=0?gcd(b,a%b):a;

}
struct node
{
	double g;
	double a;
	double b;
	int id;
}ww[maxn];
double c[maxn];//第i个的si 理应用量 <100 
bool cmp(node x,node y)
{
	return x.a*y.b>x.b*y.a;
}
int main(){		
	IO;
	freopen("burrito.in", "r", stdin);
	freopen("burrito.out", "w", stdout);
	ll n;
	double A,B;
	
	cin>>n>>A>>B;
	rep(i,1,n)
	{
		cin>>ww[i].g>>ww[i].a>>ww[i].b;
		ww[i].id=i;
	}
	sort(ww+1,ww+n+1,cmp);
	double ta=0,tb=0;
	rep(i,1,n){
		ta+=ww[i].g*ww[i].a;
		tb+=ww[i].g*ww[i].b;
		c[ww[i].id]=ww[i].g;
		if(tb>B)	//tb<=B
		{
			tb-=ww[i].g*ww[i].b;
			c[ww[i].id]=(B-tb)/ww[i].b;//实际用量si double可/0 
			tb=B;
			ta-=ww[i].g*ww[i].a;
			ta+=c[ww[i].id]*ww[i].a;
			break;
		}
	}//怒气值只要不超过上限 si尽量大 也就是ai*si开心值尽量大 
	if(ta<A){
		printf("-1 -1\n");
	}
	else{
		printf("%.9f %.9f\n",ta,tb);
		rep(i,1,n){
			printf("%.9f",c[i]);
			if(i!=n)
				printf(" ");
			else
				printf("\n");
		}
	}
	return 0;
}

上一篇:monkeyrunner 进行多设备UI测试


下一篇:在线检测显示器屏幕尺寸