SRM329div1 medium

最大値の最小化なのでセオリー通りに二分探索。

#include <algorithm>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

class LogCutter 
{
	public:

		int n;
		vector<int> canCut;

		bool check(int L,int C,int mid)
		{
			int beforeCut=0;
			while(mid<L-canCut[beforeCut] && 0<C)
			{
				if(mid<canCut[beforeCut+1]-canCut[beforeCut])
					return false;
				int nextCut=beforeCut+1;
				while(nextCut+1<n && canCut[nextCut+1]-canCut[beforeCut]<=mid)
					nextCut++;
				C--;
				beforeCut=nextCut;
			}

			return (L-canCut[beforeCut]<=mid);
		}

		string bestCut(int L, int A, int K, int C) 
		{
			long long ll=L,aa=A;
			canCut.clear();
			for(long long i=1;i<=K;i++)
				canCut.push_back((aa*i)%(ll-1)+1);
			canCut.push_back(0);
			canCut.push_back(L);
			sort(canCut.begin(),canCut.end());
			canCut.erase(unique(canCut.begin(),canCut.end()),canCut.end());
			n=canCut.size();

			int ceil=L,bottom=1;
			while(1<ceil-bottom)
			{
				int mid=(ceil+bottom)/2;
				if(check(L,C,mid))
					ceil=mid;
				else
					bottom=mid;
			}

			int opt=(check(L,C,bottom)?bottom:ceil);
			int bc=n-1,fc,fisrtCut;
			while(1)
			{
				fc=bc-1;
				while(canCut[bc]-canCut[fc-1]<=opt && 0<=fc-1)
					fc--;
				if(fc==0)
				{
					if(0<C)
						fisrtCut=1;
					else
						fisrtCut=bc;
					break;
				}
				bc=fc;
				C--;
			}
			stringstream ans;
			ans << opt << " " << canCut[fisrtCut];
			return ans.str();
		}
};