POJ3544 Journey with Pigs 动规基础贪心思想 - c++编程基础

非常经典的贪心题目，没有严格证明的话，肯定是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
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #define ll long long #define LL __int64 #define eps 1e-8 //const ll INF=9999999999999; #define inf 0xfffffff using namespace std; //vector
                
                  > G; //typedef pair
                 
                   P; //vector
                  
                   > ::iterator iter; // //map
                   
                    mp; //map
                    
                     ::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