POJ3544 Journey with Pigs 动规基础贪心思想

非常经典的贪心题目，没有严格证明的话，肯定是YY着做的，题意：

约翰要从A到B，途中会经过N个村庄，他会带N只猪，然后卖掉，每个村庄卖一只，第i个村庄的人出价pi 每斤，从A到第i个存在的距离为disi,而且运一只猪需要话花费t * disi每斤，t一开始会给定

输入第一行n,t

接下来第一行 n个数，代表各个猪的重量

在接下来第二行n个数，代表每个村庄距离A的距离dis

在接下来第三行n个数，代表每个村庄出价p

输出n个数，表示每个村庄买的哪只猪

这题目一开始看到就往dp方向去想，但是发现不行，于是大胆的YY了一把，直接按照  p - t * dis  从小到大来排序，然后猪的重量也从小到大排序，同时记录他们的编号，最后重新用一个哈希来记录即可，弄完举了几个案例发现没什么问题，就交了结果WA了，觉得自己不太对

于是就去好好的写了一下，肯定是跟 p - t * dis有关系，所以把这两列数进行了乘法运算，怎么乘岁自己，倒着，正着，然后什么都不是的，最后发现是正着的值比较高，那么我YY的就没有错，最后再仔细看题目，发现题意没理解错啊，最后看一下数据范围，发现t<=1000 000 000,这样一乘就超了32位，所以改了一下longlong，然后就过了

不错的贪心题目，多做做贪心为dp做铺垫，留着自己以后回顾看看挺不错的

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#include<cctype>
#include<queue>

#define ll long long
#define LL __int64
#define eps 1e-8

//const ll INF=9999999999999;

#define inf 0xfffffff

using namespace std;


//vector<pair<int,int> > G;
//typedef pair<int,int> P;
//vector<pair<int,int>> ::iterator iter;
//
//map<ll,int>mp;
//map<ll,int>::iterator p;

const int N = 1000 + 5;

ll n;
ll t;

typedef struct W{
	ll w;
	ll id;
};

W q[N];

typedef struct Node {
	ll dis,p;
	ll cha;//价格与距离差值
	ll id;
};

Node node[N];


void clear() {
	memset(node,0,sizeof(node));
	memset(q,0,sizeof(q));
}

bool cmp (Node x,Node y) {
	return x.cha < y.cha;
}

bool cmp1 (W x,W y) {
	return x.w < y.w;
}

int main() {
	while(scanf("%lld %lld",&n,&t) == 2) {
		ll hash[N];
		for(int i=0;i<n;i++) {
			scanf("%lld",&q[i].w);
			q[i].id = i;
		}
		for(int i=0;i<n;i++)
			scanf("%lld",&node[i].dis);
		for(int i=0;i<n;i++) 
			scanf("%lld",&node[i].p);
		for(int i=0;i<n;i++) {
			node[i].cha = node[i].p - node[i].dis * t; 
			node[i].id = i;
		}
		sort(node,node+n,cmp);
		sort(q,q+n,cmp1);
		for(int i=0;i<n;i++)
			hash[node[i].id] = q[i].id;
		for(int i=0;i<n - 1;i++)
			printf("%lld ",hash[i] + 1);
		printf("%lld\n",hash[n - 1] + 1);
	}
	return 0;
}

POJ3544 Journey with Pigs 动规基础贪心思想,布布扣,bubuko.com

POJ3544 Journey with Pigs 动规基础贪心思想

原文：http://blog.csdn.net/yitiaodacaidog/article/details/25077181