首页 > 其他分享 >1212

1212

时间:2024-01-07 18:22:24浏览次数:20  
标签:1212 满足条件 int sum mid ans now

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 9;
long long sum[maxn][maxn];
int main() {
    int n, m, c;
    cin >> n >> m >> c;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int x;
            cin >> x;
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + x;
        }
    }
    long long ans = -1, ansx, ansy;
    for (int i = c; i <= n; i++) {
        for (int j = c; j <= m; j++) {
            if (sum[i][j] - sum[i - c][j] - sum[i][j - c] + sum[i - c][j - c] > ans) {
                ans = sum[i][j] - sum[i - c][j] - sum[i][j - c] + sum[i - c][j - c];
                ansx = i, ansy = j;
            }
        }
    }
    if (ans == -1) {
        cout << ans;
    }
    else {
        cout << ans << '\n';
        cout << ansx << " " << ansy;
    }
    return 0;
}
View Code

 

 

 

 

//是不是说就是满足条件的越多,能邀请的就越多;反之则越少
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 9;
int a[maxn], b[maxn];
int n;

// 检查是否存在一种安排方式,满足条件
bool check(int mid) {
    int now = 1;    //满足条件的人数    至少有一个人参加聚会    now实际上是在考虑参与度小于 i 且符合题目要求的人数


    // 从第一个朋友开始检查
    for (int i = 1; i <= n; i++) {
        // 如果该朋友满足条件,则增加当前已确定满足条件的人数
        if (b[i] >= now - 1 && a[i] >= mid - now) now++;      //now-1是去的当前的朋友自己   mid-now  是总体答案人数减去 
    }

    // 返回是否已经满足条件的人数超过 mid
    return now > mid;
}

int main() {
    // 读入朋友的数量
    cin >> n;

    // 读入每个朋友的 ai 和 bi
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];          //比他活跃的人和不活跃的人数    
    }

    // 初始化二分查找的范围
    int l = 1, r = n, ans;

    // 二分查找
    while (l <= r) {
        // 计算中间值
        int mid = (l + r) >> 1;

        // 检查是否满足条件
        if (check(mid)) {
            // 如果满足条件,更新答案,并调整左边界
            ans = mid;
            l = mid + 1;
        }
        else {
            // 如果不满足条件,调整右边界
            r = mid - 1;
        }
    }

    // 输出最终答案
    cout << ans;
    return 0;
}
View Code

 

标签:1212,满足条件,int,sum,mid,ans,now
From: https://www.cnblogs.com/jayxuan/p/17950949

相关文章