http://acm.pku.edu.cn/JudgeOnline/problem?id=1009
Код:
#include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; int w,h,total; vector<pair<int,int> > v,ans; set<int> note; int calc_color(int x){ if(x<0 || x >= total) return -1; for(int i=0;i<v.size();i++){ if(x < v[i].second) return v[i].first; x -= v[i].second; } return -1; } #define abs(x) ((x)<0?(-(x)):(x)) void calc(){ ans.clear(); ans.push_back(make_pair(0,0)); int bef_pos = -1; for(set<int>::iterator p = note.begin();p!=note.end();p++){ int t = *p; int cur_color = calc_color(t); int around[8]; int cur_diff = 0; for(int i=0;i<8;i++) around[i] = -1; if(t % w != 0){ around[0] = calc_color(t-w-1); around[1] = calc_color(t -1); around[2] = calc_color(t+w-1); } around[3] = calc_color(t-w ); around[4] = calc_color(t+w ); if(t % w != w-1){ around[5] = calc_color(t-w+1); around[6] = calc_color(t +1); around[7] = calc_color(t+w+1); } for(int i=0;i<8;i++){ if(around[i]==-1) continue; cur_diff = max(cur_diff,abs(around[i]-cur_color)); } if(ans[ans.size()-1].first == cur_diff){ ans[ans.size()-1].second += (t-bef_pos); }else{ ans.push_back(make_pair(cur_diff,t-bef_pos)); } bef_pos = t; } } int main(void){ while(true){ cin >> w; cout << w << endl; if(w==0) break; v.clear(); total = 0; while(true){ int a,b; cin >> a >> b; if(a==0 && b == 0) break; v.push_back(make_pair(a,b)); total += b; } h = total/w; int cur_pos = 0; note.clear(); for(int i=0;i<v.size();i++){ for(int j=-w;j<=w;j+=w) for(int k=-2;k<=1;k++) note.insert(cur_pos + j + k); cur_pos += v[i].second; } note.insert(total-w); note.insert(total-w-1); note.insert(total -1); set<int>::iterator sp = note.begin(); while(*sp < 0){ note.erase(sp); sp = note.begin(); } sp = note.end();sp--; while(*sp >= total){ note.erase(sp); sp = note.end();sp--; } calc(); for(int i=0;i<ans.size();i++) if(ans[i].second != 0) cout << ans[i].first << " "<<ans[i].second << endl; cout << "0 0"<<endl; } return 0; }