第一次的代码,直接暴力,因为结果的上限就是最大值,下限是k,直接从最大值遍历到k找到答案:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int mod = 1e9+7;
typedef long long ll;
int n , m , k; // 要求的x的编号
int t[N];
int c[N];int main(){cin >> n >> m >> k;int res = 0;int num = 0;for(int i = 0 ; i < n ; i++){cin >> t[i] >> c[i];if(t[i] > num)num = t[i];}res = num;for(int i = num - 1 ; i >= 0 ; i--){int cnt = 0;for(int j = 0 ; j < n ; j++){if(t[j] == i)continue;if(t[j] > i){cnt += c[j] * (t[j] - i);}}if(cnt > m)break;else if(i < k)break;else res = i;}cout << res << endl;return 0;
}
只拿了70分,后面30分TLE了。
只好根据上下限写了个二分算法,A了。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int mod = 1e9+7;
typedef long long ll;
int n , m , k; // 要求的x的编号
int t[N];
int c[N];int main(){cin >> n >> m >> k;int res = 0;int num = 0;for(int i = 0 ; i < n ; i++){cin >> t[i] >> c[i];if(t[i] > num)num = t[i];}res = num;int l = k;int r = num;while(l < r){int mid = (l + r) >> 1;int cnt = 0;for(int j = 0 ; j < n ; j++){if(t[j] == mid)continue;if(t[j] > mid){cnt += c[j] * (t[j] - mid);}}if(cnt > m)l = mid + 1;else if(cnt < m)r = mid;else{l = r = mid;break;}}cout << l << endl;return 0;
}