C- Friends and Travel costs
题意:一共有10100+1个村庄,刚开始在0号点,每走一步花费1块钱,起始有k块钱,途中又n个朋友,跟朋友相遇时可以获得bi块钱;
题解:贪心模拟,遇到的朋友越多钱也就越多,走的也就越远;
#include <iostream>
#include <algorithm>
using namespace std;
const int N=200010;
typedef long long ll;
typedef pair<ll,ll> pll;
pll fr[N];
#define x first
#define y second
bool cmp(pll a,pll b){
return a.x<b.x;
}
int main(){
int n;
ll k;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>fr[i].x>>fr[i].y;
sort(fr+1,fr+1+n);
ll lst=0;
for(int i=1;i<=n;i++){
if(k>=fr[i].x-lst){
k-=(fr[i].x-lst);
k+=fr[i].y;
lst=fr[i].x;
}else {
break;
}
}
cout<<lst+k<<endl;
return 0;
}
D - Pond
题意:在NxN的矩阵中找到一个kxk的矩阵,并且这个矩阵的中位数高度
最小;
题解:暴力枚举肯定会超时;预处理出一个表示矩阵中大于指定高度的个数的矩阵,然后通过枚举终点获得这个对应矩阵中有多少个点大于高度中位数;最后配合二分即可;
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
const int N = 1010;
int a[N][N];
int s[N][N];
bool check(int x) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (a[i][j] > x); //预处理比x大的前缀和数组;
}
}
for (int i = m; i <= n; i++) {
for (int j = m; j <= n; j++) {
if (s[i][j] - s[i - m][j] - s[i][j - m] + s[i - m][j - m] < m * m / 2 + 1) { //判断x是否可以作为第m*m/2+1个元素;
return true;
}
}
}
return false;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
int l = 0, r = 1e9;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) r=mid;
else l = mid + 1;
}
cout << r << endl;
return 0;
}