POJ2393

POJ2393

2393 -- Yogurt factory

一週間ぶりくらいですね 今回は貪欲法の練習として解きました

ヒントに32bitより大きい整数になるかもしれないぞって書いてあるのにそれに気づかず悩んでました。

考え方としては、その週で買ったコストと保存しておくコストの和と、出荷する週で買ったコストのどちらが小さいかを選択していきました。 直感的な数学力のなさから最初は何個か保存しておいて足りない分を出荷する週で買う場合も存在するのかなって思ったので、微分して確かめたりしました。

あと、最初英語がよくわからなくて英語頑張らないとなあと思いました

解答時間は50分です。 以下コードです

#include <stdio.h>

int n, s, store = 0;
int y[10000], c[10000];
long long cost = 0;

long long solve(){
  for(int i = 0; i < n; i++){
    cost += store * s;
    if(y[i] > store){
      cost += (y[i] - store) * c[i];
      store = 0;
    }else{
      store -= y[i];
    }
    for(int j = i+1; j < n; j++){
      if(c[j] - c[i] - s * (j - i) > 0){
        cost += y[j] * c[i];
        store += y[j];
      }else{
        break;
      }
    }
  }
  return cost;
}

int main(){
  scanf("%d %d", &n, &s);
  for(int i = 0; i < n; i++){
    scanf("%d %d", &c[i], &y[i]);
  }
  printf("%lld\n", solve());
  return 0;
}