Description

在小X 的家鄉，有機房一條街，街上有很多機房。每個機房里都有一萬個人在切題。小X 剛刷完CodeChef，準備出來逛逛。
機房一條街有n 個機房，第i 個機房的坐標為xi，小X 的家坐標為0。小X 在街上移動的速度為1，即從x1 到x2 所耗費的時間為 |x1?x2|。
每個機房的學生數量不同，ACM 題目水平也良莠不齊。小X 到達第i 個機房后，可以花ti 的時間想題，然后瞬間AK；當然，也可以過機房而不入。
小X 現在只有m 個單位時間，之后他就該趕著去打Codeforces 了。現在他想知道自己最多能在多少個機房AK，希望你幫幫他。

Input

第一行包含兩個整數n;m。
接下來n 行，每行包含兩個整數xi; ti。

Output

第一行包含一個整數，表示小X 最多能AK 的機房數量。

Sample Input

2 10
1 100
5 5

Sample Output

1

Data Constraint

對于30% 的數據，n≤20。
對于60% 的數據，n≤1000。
對于100% 的數據，1≤n≤105，0≤m;xi≤1018，0≤ti≤109。

Solution

• 這題給人的第一感覺就是貪心

• 當然首先要按每個點的坐標排序了

• 顯然他是不可能往回走的

• 那么很容易想到，當他走到一個點 i 時，

• 只需從 1?n 中選出一些數，使得總和小于等于 m?ti ，讓這些數的個數最多

• 那么顯然選最小的那幾個，并且使得總和小于等于 m?ti 即可

• 于是維護一個從小到大的 時間表，每次累加最小并符合條件的那幾個

• 維護時使用插入排序，時間復雜度 O(n2)

• 但是一看數據范圍： n≤105 ！！！肯定過不了~~~

• 把思路回到維護時間表那里，每次插入排序顯然效率超低，又維護了不少的無關量

• 首先大到使總和超過 m?ti 的那些數可以直接舍去

• 剩下的即為要選的，之后當遇到一個時間 ti 時，

• 把當前要選的數之中最大的給替換成 ti ，那么答案便最優了

• 這樣累加的時間復雜度就是 O(nlogn) ！

Code

#include<cstdio> #include<algorithm> using namespace std; const int N=100001; struct data {long long x;int y; }a[N]; int ans,n,f[N]; long long sum,m; inline bool cmp(data a,data b){return a.x<b.x;} int main() {scanf("%d%lld",&n,&m);for(int i=1;i<=n;i++) scanf("%lld%d",&a[i].x,&a[i].y);sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++)if(sum+a[i].y<=m-a[i].x){sum+=f[++f[0]]=a[i].y;ans++;}elseif(a[i].y<f[f[0]]){sum-=f[f[0]]-a[i].y;f[f[0]]=a[i].y;}printf("%d",ans);return 0; }

總結

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

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