没有任何算法的一道，ac 秘诀在于步骤要清晰，尽量简明思路。

聪明的小朋友肯定想到了用行内前缀和，来判断该行区间是否全部能放人。

还有通过每列的前缀最大值，来判断当前格子能不能放这个高度的人。

同时可以给当前行选择区间的前缀最大值排序，和已经排序的 h 数组一个个相应下标匹配，但凡一个出问题，直接否定整个区间。

好了，打出来却发现 WA 和 TLE 找上门。

考虑优化，假设列区间已经固定，如果 i 行这个区间可以放人，那么 i 后面的行这个区间只要空的都可以放人。

即判断能否放人的列区间具有单调性。

直接二分可以放人的行边界，这个时候先只关注前缀最大值，最后累计答案时再关注空不空。

复杂度因为要二分和排序，是枚举 * 双 log，也就是 $O(N^2log^2N)$。

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

typedef long long LL;
const int N = 2010;

LL a[N][N];
LL sum[N][N];
LL mx[N][N];
LL h[N];
LL now[N];
int n, m, K;

bool check(int x, int y) {
	for (int j = y; j <= y + K - 1; j ++) {
		now[j - y + 1] = mx[x][j];
	}
	sort(now + 1, now + K + 1);
	for (int i = 1; i <= K; i ++) {
		if (h[i] <= now[i]) {
			return 0;
		}
	}
	return 1;
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m >> K;
	
	for (int i = 1; i <= K; i ++) {
		cin >> h[i];
	}
	sort (h + 1, h + K + 1);
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			cin >> a[i][j];
		}
	}
	
	for (int i = 1; i <= n; i ++) {
		sum[i][0] = 0;
		for (int j = 1; j <= m; j ++) {
			sum[i][j] = sum[i][j - 1] + a[i][j];
		}
	}
	
	for (int j = 1; j <= m; j ++) {
		mx[0][j] = 0;
		for (int i = 1; i <= n; i ++) {
			mx[i][j] = max(mx[i - 1][j], a[i][j]);
		}
	}
	
	int ans = 0;
	for (int j = 1; j + K - 1 <= m; j ++) {
		int l = 1, r = n, p = 1;
		int mid;
		while (l <= r) {
			mid = (l + r) >> 1;
			if (check(mid, j)) {
				l = mid + 1;
				p = mid;
			}
			else {
				r = mid - 1;
			}
		}
		
		for (int i = 1; i <= p; i ++) {
			if (sum[i][j + K - 1] - sum[i][j - 1] == 0) {
				ans ++;
			}
		}
	}
	
	cout << ans << "\n";
	
	return 0;
} 

题目传送门

思路

我们可以先用一个二维数组存下每个座位正前方所有同学的最大身高，由于该数组中每一列从小到大单调不减，考虑对行二分，再暴力地排序比较，判断是否可以全部坐下即可。复杂度 $O(mk\log k \log n)$，可以通过。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k,ans;
int a[2005];
int p[2005][2005];     //p用来存该座位前方最大身高
int q[2005];           //q用于排序
int o[2005][2005];     //o是每排前缀和，用于快速判断是否合法
int g[2005][2005];
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++) cin>>a[i];
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {
		cin>>g[i][j];
		p[i][j]=max(p[i-1][j],g[i][j]);
        o[i][j]=o[i][j-1]+g[i][j];
	}
    //对a排序，方便比较
	sort(a+1,a+k+1);
	for (int j=k;j<=m;j++){
		int l=1,r=n,Rx=1;
        //二分行
		while(l<=r){
			int mid=(l+r)>>1;
			for(int w=1;w<=k;w++){
				q[w]=p[mid][j-w+1];
			}
			sort(q+1,q+k+1);
			bool f=0;
			for(int w=1;w<=k;w++){
				if(q[w]>=a[w]){
					f=1;break;
				}
			}
			if(f){
				r=mid-1;
			}
			else{
				l=mid+1;
				Rx=mid;
			}
		}
        //判断是否是连续的空座位
		for(int i=1;i<=Rx;i++){
			if(o[i][j]-o[i][j-k]==0) ans++;
		}
	} 
	cout<<ans;
	return 0;
}

完结撒花！！！