Beta Round #64-B: Text Messaging
解法
実装するだけ。スペースを消去できるのはmessage間だけ(text間ではない)ことに気づかなかったけどcodeforcesにしては珍しくpretestで弾いてくれた。
#include <cstdio> #include <algorithm> #include <vector> #include <string.h> #include <iostream> using namespace std; char str[100009]; int N; int solve(){ vector<int> ns, ws, ls; //ns.push_back(-1); for(int i=0; i<strlen(str); i++){ if(str[i] == '.' || str[i] == '?' || str[i] == '!'){ ns.push_back(i); } if(str[i] != ' '){ ws.push_back(i); } } for(int i=0; i<ns.size(); i++){ int u = i>0?*upper_bound(ws.begin(), ws.end(), ns[i-1]):ws[0]; int v = *lower_bound(ws.begin(), ws.end(), ns[i]); if(v - u + 1 > N) return -1; } int ans = 1, cur = 0, pre=ws[0]; for(int i=0; i<ns.size(); i++){ int post = *lower_bound(ws.begin(), ws.end(), ns[i]); if(post - pre + 1<= N){ cur = post - pre + 1; } else{ ans++; pre = *upper_bound(ws.begin(), ws.end(), ns[i-1]); } } return ans; } int main(){ scanf("%d ",&N); gets(str); int ans = solve(); if(ans<0){ puts("Impossible"); } else{ printf("%d\n",ans); } return 0; }