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