Greedy:Yogurt factory(POJ 2393)

　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　酸奶工厂

　　题目大意：酸奶工厂每个星期都要制造酸奶，成本每单位x，然后每个星期要生产y，然后酸奶厂有个巨大的储存室，可以无限储存酸奶，而且酸奶的品质不会变坏，每天储存要每单位花费S，求最小的成本。

　　简直是初中生数学题，贪心法即可，假如当前酸奶成本是X，则如果储存酸奶，则下k个星期的（如果还使用这批酸奶），则成本为x+k*s，对比k个星期的成本就可以确定用哪个了。

　　水题

 #include <iostream>

 #include <functional>

 #include <algorithm>

 typedef struct demand

 {

     int cost;

     int units;

 }Week;

 Week work[];

 void Search(const int, const int);

 int main(void)

 {

     int N, S;

     while (~scanf("%d%d", &N, &S))

     {

         for (int i = ; i < N; i++)

             scanf("%d%d", &work[i].cost, &work[i].units);

         Search(N, S);

     }

     return ;

 }

 void Search(const int N, const int S)

 {

     int stop, now_cost, j;

     long long ans = ;

     for (int pos = ; pos < N; )

     {

         now_cost = work[pos].cost;

         for (stop = pos + , j = ; stop < N && now_cost + j*S < work[stop].cost; j++, stop++);

         for (int k = ; k < j; k++)//i是当前位置

             ans += (long long)((now_cost + S*k) * work[pos + k].units);

         pos = stop;

     }

     printf("%lld\n", ans);

 }