[ create a new paste ] login | about

Link: http://codepad.org/uLTQwvGC    [ raw code | output | fork ]

C++, pasted on Feb 27:
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
using namespace std;
typedef long long ll;

#define SZ(a) ((int)a.size()) 

class SentenceSplitting {
public:
	int split(string sentence, int K) {

		int mi = 1;
		int ma = 50;
		int longest_row;

//		for(int i=0;i<100;i++) これでもOK
//		while(mi<=ma) これはNG。無限ループになる。
		while(mi<ma) // これは、最後にlongest_row = (mi+ma)/2を足せばOK
		{
			longest_row = (mi+ma)/2;
			cout << " min=" << mi << " max=" << ma << " longest_row=" << longest_row << "\n";

			// K回くぎりでlongest_rowの中におさまるか?
			string::size_type st=0;
			int k = K;
			bool b_osamaru = false;
			do
			{
				if(longest_row>=SZ(sentence)-(int)st)
				{
					b_osamaru = true;
					break;
				}

				// おさまらなかった場合でも、くぎればおさまるチャンスあり

				// くぎあったあとのせんとうのもじをさがす。" "でくぎるので、そのつぎのもじ
				st = sentence.find_last_of(" ",st+longest_row);
				if(st==string::npos)
				{
					// もうくぎれない。文字が短くならない。無理。
					break;
				}
				else
				{
					// " "のつぎから
					st++;
				}

			} while(k--);

			if(b_osamaru)
			{
				ma = longest_row;
			}
			else
			{
				mi = longest_row + 1; // 1は忘れないように!。足さないとmiとmaが1差になって、b_osamaru=falseのとき収束しない。
			}
		}

		longest_row = (mi+ma)/2; // while(mi<ma)のとき必要。
		cout << "Last min=" << mi << " max=" << ma << " longest_row=" << longest_row << "\n";


		return longest_row;
	}

};


Output:
1
2
Line 21: error: ISO C++ does not support 'long long'
compilation terminated due to -Wfatal-errors.


Create a new paste based on this one


Comments: