Atcode abc203 CD

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;
}
上一篇:7.1.2 Python 数据结构《字符串》格式输出,下标切片,函数《元组》定义,操作,遍历《列表》定义,增删改查,函数,列表表达式《字典》定义,增删改查,遍历,函数《集合》定义,遍历,增删改查,函数


下一篇:你必须熟练使用的30个有用Python代码片段