| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:简单的贪心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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator