Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:简单的贪心

Posted by KatrineYang at 2016-08-31 04:58:08 on Problem 3544
In Reply To:简单的贪心 Posted by:Gin_dl at 2008-04-24 14:37:23
> 贪心算法,就是根据某个数学不等式,具体名字忘记了,内容是逆序积的和<=乱序的<=顺序的
> 不过这个要考虑计算实际价格的时候中间计算结果超过32bit整数的情况,不然就得郁闷的wa好几次。。
车比雪夫吧?
附代妈
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

long long int N, T;
long long int W[1010], D[1010], P[1010], L[1010];

bool compareL(int i1, int i2){
	return L[i1] < L[i2];
}

bool compareW(int i1, int i2){
	return W[i1] < W[i2];
}

int main() {
	scanf("%I64d%I64d", &N, &T);
	for(int i = 1; i <= N; i++) scanf("%I64d", &W[i]);
	for(int i = 1; i <= N; i++) scanf("%I64d", &D[i]);
	for(int i = 1; i <= N; i++) scanf("%I64d", &P[i]);
	for(int i = 1; i <= N; i++) L[i] = P[i] - D[i] * T;
	int ordW[1010], ordL[1010];
	for(int i = 1; i <= N; i++) ordW[i] = i;
	for(int i = 1; i <= N; i++) ordL[i] = i;
	sort(ordW+1, ordW+N+1, compareW);
	sort(ordL+1, ordL+N+1, compareL);
	int ans[1010];
	for(int i = 1; i <= N; i++){
		ans[ordL[i]] = ordW[i];
	}
	for(int i = 1; i <= N; i++){
		printf("%d", ans[i]);
		if(i != N) printf(" ");
	}
	printf("\n");
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator