codeforces 803D Magazine Ad

D. Magazine Ad
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
The main city magazine offers its readers an opportunity to publish their ads. The format of the ad should be like this:
There are space-separated non-empty words of lowercase and uppercase Latin letters.
There are hyphen characters '-' in some words, their positions set word wrapping points. Word can include more than one hyphen.
It is guaranteed that there are no adjacent spaces and no adjacent hyphens. No hyphen is adjacent to space. There are no spaces and no hyphens before the first word and after the last word.
When the word is wrapped, the part of the word before hyphen and the hyphen itself stay on current line and the next part of the word is put on the next line. You can also put line break between two words, in that case the space stays on current line. Check notes for better understanding.
The ad can occupy no more that k lines and should have minimal width. The width of the ad is the maximal length of string (letters, spaces and hyphens are counted) in it.
You should write a program that will find minimal width of the ad.
Input
The first line contains number k (1 ≤ k ≤ 105).
The second line contains the text of the ad — non-empty space-separated words of lowercase and uppercase Latin letters and hyphens. Total length of the ad don't exceed 106 characters.
Output
Output minimal width of the ad.
Examples
input
4
garage for sa-le
output
7
input
4
Edu-ca-tion-al Ro-unds are so fun
output
10
Note
Here all spaces are replaced with dots.
In the first example one of possible results after all word wraps looks like this:
garage.
for.
sa-
le
The second example:
Edu-ca-
tion-al.
Ro-unds.
are.so.fun
제목: 문자열을 주면 빈칸과'-'가 분리되어 그룹 수가 k보다 적은 상황에서 가장 작은 그룹 너비 사고방식: 2점+욕심판단;2분 동안 우리는 직접 답을 나누고 가장 길면mid를 나눌 수 있다고 가정한 다음에 욕심을 부리는 사상을 이용하여 이런 그룹의 수가 k보다 작은지 검증한다. 만약에 그룹의 수가 k보다 크면 결과가 너무 작고low=mid+1이다. 그렇지 않으면 결과가 너무 크다는 high=mid-1이다.이렇게 마지막 low는 결과이다. 욕심을 부릴 때 우리는 연속적인mid의 자모에''와'-'가 포함되어 있는지 판단해야 한다. 만약에 포함된다면 그룹수 +1, 포함하지 않고 문자열의 끝에 이르지 못하면 이런 길이가 너무 짧아false로 돌아가 구체적으로 코드를 볼 수 있다.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int max_n = 5;
int k;
char c[1000006];
int numa,numb;
int len;
bool judge(int mid) {
    int cnt = 0;
    int t = 0;
    int j;
    for(int i = 0; i < len;) {
        int flag = 0;
        for( j=i; j < i+mid && j < len; ++j) {
            if(c[j] ==' ' || c[j] == '-') {
                flag = 1;
                t = j;
            }
        }
        if(flag) {
            cnt++;
            if(j == len){
                i = j;
            }else{
                i = t+1;
            }
        }else {
            if(j == len){
                cnt++;
                i = j;
            }else{
                return false;
            }
        }
    }
    if(cnt <= k) {
        return true;
    }
    return false;
}

int main() {
    cin >> k;
    getchar();
    gets(c);
    len = strlen(c);
    int low = 0;
    int high = len;
    int mid;
    while(low <= high) {
        mid = (low+high)/2;
        if(judge(mid)) {
            high = mid-1;
        } else {
            low = mid+1;
        }
    }
    printf("%d
",low); return 0; }

주의: 출력은low이지 mid가 아닙니다

좋은 웹페이지 즐겨찾기