题目描述
暴力70分
样例
/*
暴力做法;
数组存放(ti, ci),每次循环先sort(flag, ti降序,ci升序),若存在,m -= ci, ti -= 1
这里的flag意思是若t1 <= k,flag = 0, 排序放到后面
若不存在,return 排序好后的arr[0].t1即T_total
时间复杂度为:m * sort
至此,csp系统里是70分,AcWing只过了3个数据;
*/
#include<iostream>
#include<algorithm>
#include<utility>
using namespace std;
int n, m, k;
const int N = 100010;
struct node{
int t, c, flag;
}p[N];
bool cmp(node s1, node s2){//flag = 1, 若s的ti <= k, 则他的flag = 0
if(s1.flag != s2.flag) return s1.flag > s2.flag;
else if(s1.t != s2.t) return s1.t > s2.t;
else return s1.c < s2.c;
}
int main(){
cin >> n >> m >> k;
for(int i = 0; i < n; i++){
cin >> p[i].t >> p[i].c;
p[i].flag = p[i].t > k ? 1 : 0;
}
while(m > 0){
sort(p, p + n, cmp);
if(p[0].flag == 0) break;//已经调整好
else{
if(m > p[0].c) m -= p[0].c;
else break;
p[0].t--;
if(p[0].t == k) p[0].flag = 0;
}
}
sort(p, p + n, cmp);
cout << p[0].t;
return 0;
}
二分100分
/*
暴力做法;
数组存放(ti, ci),每次循环先sort(flag, ti降序,ci升序),若存在,m -= ci, ti -= 1
这里的flag意思是若t1 <= k,flag = 0, 排序放到后面
若不存在,return 排序好后的arr[0].t1即T_total
时间复杂度为:m * sort
至此,csp系统里是70分,AcWing只过了3个数据;
因为m是10^9,所以肯定过不了,改进想法是如果对于每个(ti, ci),都能快速求出ti减去的数量,时间复杂度就和m无关了
二分,全都缩小到x天, [k, p[0].t],
check: sum((p[i].t - x) * p[i].c) <= m,这里注意需要用long long
这样结束,csp里100分
*/
#include<iostream>
#include<algorithm>
using namespace std;
int n, m, k;
const int N = 100010;
struct node{
int t, c;
}p[N];
bool check(int u){
long long res = 0;
for(int i = 0; i < n; i++){
if(p[i].t <= u) continue;
res += (p[i].t - u) * p[i].c;
}
if(res <= m) return true;
else return false;
}
int b_search(int max_t){
int l = k, r = max_t;
while(l < r){
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
int main(){
cin >> n >> m >> k;
int max_t = 0;
for(int i = 0; i < n; i++){
cin >> p[i].t >> p[i].c;
max_t = max(max_t, p[i].t);
}
cout << b_search(max_t);
return 0;
}