naoya_t@topcoder

SRM373 Div1 Easy: StringFragmentation

過去問, 練習 | 04:51 |

• 幅も高さも10000までなので、ポイント数を上限（高々9998）から1ptずつデクリメントしつつ（8ptまで）全て試せる
• Passed System Test223.65点
• 9'46''

#define sz(a)  int((a).size())
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

class StringFragmentation {
 public:
  int largestFontSize(string text, int width, int height) {
    vector<string> words=split(text);
    int n=sz(words);
    int longest=0;
    tr(words,it) longest=max(sz(*it),longest);
    int pt_max=(10000/longest)-2;
    for(int pt=pt_max;pt>7;pt--){
      int x=0,y=pt*2;
      rep(i,n){
        const string word=words[i];
        int w=sz(word)*(pt+2);
        x+=w;
        if(x>width){
          y+=pt*2; x=w;
          if(x>width) goto next;
        }
        x+=(pt+2);
      }
      if(y<=height) return pt;
   next:;
    }
    return -1;
  }
};