小 X 的 AK 計劃

題目大意：

有n個點，到一個點（時間為距離）并花一些時間可以A掉此點，問最多可以A多少個點

原題：

解題思路：

先按位置從小到大排序，然后到每一個點并A掉的時間加在一起，當大于m時，把A掉的點中花費時間最多的去除掉（用STL的大根堆來處理）

代碼：

#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; long long n,m,x,y,l,sum,num,ans; struct rec {long long v,t; }a[100005]; bool cmp(rec xx,rec yy) {return xx.v<yy.v; } int main() {scanf("%lld %lld",&n,&m);for (int i=1;i<=n;++i){scanf("%lld %lld",&x,&y);if (x+y>m)continue;//優化，感性理解a[++l].v=x;a[l].t=y;}sort(a+1,a+1+l,cmp);//排序priority_queue<int>d;//大根堆for (int i=1;i<=l;++i){sum+=a[i].t+a[i].v-a[i-1].v;//加在一起d.push(a[i].t);//入堆num++;if (sum>m){sum-=d.top();//減去d.pop(); //出堆num--;}ans=max(ans,num);//求最大}printf("%lld",ans);//輸出 }

總結

以上是生活随笔為你收集整理的小 X 的 AK 计划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。