H: 小明的比賽

內(nèi)存限制：128 MB時(shí)間限制：1 S標(biāo)準(zhǔn)輸入輸出

題目描述

小明的算法競(jìng)賽水平很高，他經(jīng)常參加網(wǎng)上的比賽。
比賽的規(guī)則是這樣的：要在規(guī)定時(shí)間內(nèi)解決 n 道題，解決時(shí)間越晚失去的分?jǐn)?shù)就越多。
當(dāng)然如果有錯(cuò)誤提交還會(huì)扣額外的分?jǐn)?shù)。為了簡(jiǎn)化題目，我們假設(shè)小明所有題目都可以一遍 AC。
小明實(shí)在是太強(qiáng)了，以致于他看完所有題目就都會(huì)做了。剩下的就是把它們寫出來(lái)的問(wèn)題。小明掐指一算，算出了寫每道題需要的時(shí)間 Ti，以及每道題每分鐘會(huì)失去的分?jǐn)?shù) Ai。也就是說(shuō)，如果他在 x 分鐘時(shí)完成這道題，他將失去 x * Ai 的分?jǐn)?shù)。
請(qǐng)合理安排做題順序，使得當(dāng)小明做完比賽時(shí)，失去的分?jǐn)?shù)盡可能少。

輸入格式

第一行給出一個(gè)正整數(shù) T(T<=10)，表示數(shù)據(jù)組數(shù)。
對(duì)于每組數(shù)據(jù)，第一行一個(gè)正整數(shù) n，表示這場(chǎng)比賽的題目數(shù)。第二行 n 個(gè)整數(shù)，表示做每道題需要的時(shí)間 Ti。第三行 n 個(gè)整數(shù)，表示每題每分鐘失去的分?jǐn)?shù) Ai。
其中：0<n<=100000，0<Ti,Ai<=10000

輸出格式

對(duì)于每組數(shù)據(jù)，輸出一個(gè)整數(shù)，表示最少失去的分?jǐn)?shù)。

輸入樣例 復(fù)制

1
3
10 10 20
1 2 3

輸出樣例 復(fù)制

150

思路：這種題很顯然得看每一個(gè)題的每分鐘權(quán)重分值大小來(lái)決定先后寫的順序的，權(quán)重大的先做，感覺(jué)是很常見(jiàn)的題目了。

代碼：

#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;
}