SRM 647 Div2 Medium TravellingSalesmanEasy

問題

SRM 647 - TopCoder Wiki

あるセールスマンはcity[i]だけで売ることが出来るprofit[i]の利益が出る商品を持っている. 今visit[i]の街を訪れることが確定している時,最大の利益を答える問題.

解答

  • Easyかと疑うレベル
  • 訪れる街で売れる商品の一番利益の高いものから順に売っていけば良い
using namespace std;

class TravellingSalesmanEasy
{
public:
  int getMaxProfit(int M, vector <int> profit, vector <int> city, vector <int> visit)
    {
      vector<vector<int> > p(M+1, vector<int>(0));
      int i;
      int n = profit.size();
      for (i = 0; i < n; i++) p[city[i]].push_back(profit[i]);
      for (i = 0; i <= M; i++) sort(p[i].rbegin(), p[i].rend());
      vector<int> counter(M+1, 0);
      int res = 0;
      for (int i = 0; i < visit.size(); i++) {
        if (counter[visit[i]] < p[visit[i]].size()) {
          res += p[visit[i]][counter[visit[i]]];
          counter[visit[i]]++;
        }
      }
      return res;
    }
};