排序+贪心错在哪了
/*
* 最优比第一次尝试:按p/r排序
* 最优比第二次尝试:(a.r+b.r)*b.p + a.r*a.p < (a.r+b.r)*a.p + b.r*b.p (a先做的消耗小于b先做的消耗)
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 50 + 5;
struct node
{
int max; //分数
int poi; //每分钟减少的分数
int req; //花费的时间
double opt; //最优比
}arr[maxn];
int n, t;
long long ans = 0;
long long cnt = 0;
bool cmp(node a, node b)
{
if(a.opt == b.opt)
{
if(a.max == b.max) return a.req < b.req;
else return a.max > b.max;
}
else return a.opt > b.opt;
}
int main()
{
//1 输入
//1.1 第一行输入两个整数N,T (1 ≤ N ≤ 50, 1 ≤ T ≤ 100000)
scanf("%d%d", &n, &t);
//1.2 第二行输入n个整数maxPoints[i]
for(int i = 1; i <= n; i++)
scanf("%d", &arr[i].max);
//1.3 第三行输入n个整数pointsPerMinute[i]
for(int i = 1; i <= n; i++)
scanf("%d", &arr[i].poi);
//1.4 第四行输入n个整数requiredTime[i]
for(int i = 1; i <= n; i++)
scanf("%d", &arr[i].req);
//2 按最优比排序
//2.1 求最优比
for(int i = 1; i <= n; i++)
arr[i].opt = 1.0 * arr[i].poi / arr[i].req;
//2.2 按最优比由大到小排序
sort(arr + 1, arr + n + 1, cmp);
//3 贪心求最大分值
long long temp;
for(int i = 1; i <= n; i++)
{
//3.1 求这道题的最终得分
//3.1.1 如果这道题做不完,直接跳过
if(cnt + arr[i].req > t) continue;
//3.1.2 否则能做完,做一下试试
temp = arr[i].max - arr[i].poi * (cnt + arr[i].req);
//3.2 如果最终得分为正,则做这道题,否则不做
if(temp > 0)
{
ans += temp;
cnt += arr[i].req;
}
}
//4 输出最大分值
printf("%lld\n", ans);
return 0;
}
* 最优比第一次尝试:按p/r排序
* 最优比第二次尝试:(a.r+b.r)*b.p + a.r*a.p < (a.r+b.r)*a.p + b.r*b.p (a先做的消耗小于b先做的消耗)
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 50 + 5;
struct node
{
int max; //分数
int poi; //每分钟减少的分数
int req; //花费的时间
double opt; //最优比
}arr[maxn];
int n, t;
long long ans = 0;
long long cnt = 0;
bool cmp(node a, node b)
{
if(a.opt == b.opt)
{
if(a.max == b.max) return a.req < b.req;
else return a.max > b.max;
}
else return a.opt > b.opt;
}
int main()
{
//1 输入
//1.1 第一行输入两个整数N,T (1 ≤ N ≤ 50, 1 ≤ T ≤ 100000)
scanf("%d%d", &n, &t);
//1.2 第二行输入n个整数maxPoints[i]
for(int i = 1; i <= n; i++)
scanf("%d", &arr[i].max);
//1.3 第三行输入n个整数pointsPerMinute[i]
for(int i = 1; i <= n; i++)
scanf("%d", &arr[i].poi);
//1.4 第四行输入n个整数requiredTime[i]
for(int i = 1; i <= n; i++)
scanf("%d", &arr[i].req);
//2 按最优比排序
//2.1 求最优比
for(int i = 1; i <= n; i++)
arr[i].opt = 1.0 * arr[i].poi / arr[i].req;
//2.2 按最优比由大到小排序
sort(arr + 1, arr + n + 1, cmp);
//3 贪心求最大分值
long long temp;
for(int i = 1; i <= n; i++)
{
//3.1 求这道题的最终得分
//3.1.1 如果这道题做不完,直接跳过
if(cnt + arr[i].req > t) continue;
//3.1.2 否则能做完,做一下试试
temp = arr[i].max - arr[i].poi * (cnt + arr[i].req);
//3.2 如果最终得分为正,则做这道题,否则不做
if(temp > 0)
{
ans += temp;
cnt += arr[i].req;
}
}
//4 输出最大分值
printf("%lld\n", ans);
return 0;
}