H: 小明的比赛
H: 小明的比赛
内存限制：128 MB时间限制：1 S标准输入输出
题目描述
小明的算法竞赛水平很高，他经常参加网上的比赛。
比赛的规则是这样的：要在规定时间内解决 n 道题，解决时间越晚失去的分数就越多。
当然如果有错误提交还会扣额外的分数。为了简化题目，我们假设小明所有题目都可以一遍 AC。
小明实在是太强了，以致于他看完所有题目就都会做了。剩下的就是把它们写出来的问题。小明掐指一算，算出了写每道题需要的时间 Ti，以及每道题每分钟会失去的分数 Ai。也就是说，如果他在 x 分钟时完成这道题，他将失去 x * Ai 的分数。
请合理安排做题顺序，使得当小明做完比赛时，失去的分数尽可能少。
输入格式
第一行给出一个正整数 T(T<=10)，表示数据组数。
对于每组数据，第一行一个正整数 n，表示这场比赛的题目数。第二行 n 个整数，表示做每道题需要的时间 Ti。第三行 n 个整数，表示每题每分钟失去的分数 Ai。
其中：0<n<=100000，0<Ti,Ai<=10000
输出格式
对于每组数据，输出一个整数，表示最少失去的分数。
输入样例 复制
1
3
10 10 20
1 2 3
输出样例 复制
150
思路：这种题很显然得看每一个题的每分钟权重分值大小来决定先后写的顺序的，权重大的先做，感觉是很常见的题目了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=30050;
int n,m;
int t;
double a,b;
struct node
{
int t;
int fen;
double bi;
}ti[100005];
bool comp(node a,node b)
{
return a.bi>b.bi;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&ti[i].t);
}
for(int i=0;i<n;i++)
{
scanf("%d",&ti[i].fen);
ti[i].bi=(double)ti[i].fen/(double)ti[i].t;
}
sort(ti,ti+n,comp);
long long tim=0;
long long fin=0;
for(int i=0;i<n;i++)
{
tim+=ti[i].t;
fin+=tim*ti[i].fen;
}
printf("%lld\n",fin);
}
return 0;
}
评论