解いた問題のソースコードと解説など。


SRM 415 Div1 easy ShipLoading

持ち上げられるクレーンの重さでソートし、荷物を持ち上げることのできるクレーンで使用回数(秒数)がもっとも少ないものに順繰りに荷物を割り振っていく。最終的にもっとも使用したクレーンの回数が答え。

  int minimumTime(vector <int> cranes, vector <string> boxes){
    string s;
    vector<int> weight;
    for(int i = 0; i < (int)boxes.size(); i++)
      s += boxes[i];

    stringstream ss;
    ss << s;
    int x;
    while(ss >> x) weight.push_back(x);

    sort(cranes.begin(), cranes.end());
    sort(weight.begin(), weight.end(), greater<int>());
    vector<int> cnt(cranes.size(), 0);
    
    for(int i = 0; i < weight.size(); i++){
      int idx = -1;
      int mincnt = INF;
      for(int j = 0; j < cranes.size(); j++){
	if(cranes[j] >= weight[i] && mincnt > cnt[j]){
	  mincnt = cnt[j];
	  idx = j;
	}
      }
      if(idx == -1) return -1;
      cnt[idx]++;
    }

    cout << weight.size() << endl;
    return *max_element(cnt.begin(), cnt.end());
  }

SRMばっかやっていてPOJがおろそか。

Get up! 明日のSUPER ST@R!