Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:此题略坑 细节很多In Reply To:此题略坑 细节很多 Posted by:BJ061008mms at 2015-04-12 15:49:08 > #include <iostream> > #include <queue> > #include <algorithm> > using namespace std; > struct _pair { > int a; > int b; > }; > bool cmp(const _pair& left, const _pair& right){ > return left.a < right.a; > } > int main(){ > int N; > cin>>N; > _pair *t = new _pair[N]; > for(int i=N-1;i>=0;i--){ > cin >> t[i].a >> t[i].b; > } > int L ,P; > cin>> L >> P; > for (int i =N-1;i>=0;i--) { > t[i].a = L-t[i].a; > } > sort(t,t+N,cmp); > priority_queue<int> que; > que.push(P); > int cur = 0,ii=0,count=0; > while(!que.empty()) { > cur+=que.top();que.pop(); > if (cur>=L) break; > count++; > while(t[ii].a<=cur && ii<N) { > que.push(t[ii].b);ii++; > } > > } > > if(cur>=L) > printf("%d\n", count); > else > puts("-1"); > > delete[] t; > > return 0; > } > //=============================== > 1 输入的不是距离开始位置的距离,是相对结尾的距离 > 2 距离不一定是有序的要人工排序 > 3 没有结果输出-1 的格式很怪,但puts能搞定 真的是神坑啊。一开始注意到第一点,怎么也想不通样例。第二点也是坑,没事考排序干嘛。 谢谢大神提醒。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator