Codeforces Global Round 16 D2. Seating Arrangements (hard version) 模拟 + 贪心 + 二分

贪心 + 二分"/>

Codeforces Global Round 16 D2. Seating Arrangements (hard version) 模拟 + 贪心 + 二分

题目链接

题目大意

有一个n行m列的表格

有n*m个人 每个人都有一个等级ai 题目中给出

对于任意两个人 i j 若ai>aj 则si>sj

其中si=第i个人坐的位置

假设坐(x,y) si= x*m+j

从1-n*m开始选座位 一个人进入每行时 他的不舒服程度 = 该行前面的的人数

问你最小不舒服程度

题目思路

模拟 用abc三个数组存a1

其中b用来sort 得到最后的座位图

c用来判断该位置有没有坐人

对于每一个i 先二分出在b数组的位置

然后去判断应该坐哪个位置

通过贪心思想可得知 在b数组中 若该数字有多个位置 应该尽量从包含该数字的最小的一行靠右面的位置开始坐 这样会使最后的不舒服程度最小

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=310;
const int maxm=1e5+10;
int n,m;
int T;
int a[maxm];
int b[maxm];
int c[maxm];
void init()
{for(int i=0;i<=n*m;i++){a[i]=b[i]=c[i]=0;}
}
int main()
{cin>>T;while(T--){cin>>n>>m;ll ans=0;init();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[(i-1)*m+j];b[(i-1)*m+j]=a[(i-1)*m+j];}}sort(b+1,b+n*m+1);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int val=a[(i-1)*m+j];int pos=upper_bound(b+1,b+n*m+1,val)-b;pos--;int hang=((pos-1)/m);int thang=hang;while(thang>=1&&b[(thang)*m]==val)thang--;//找到存在该val的最后一行 int ppos;for(int k=thang*m+m;k>thang*m;k--){if(b[k]==val&&c[k]==0){c[k]=1;	ppos=k;break;}else if(k==thang*m+1) //如果该行已填满 跳到下一行 {thang++;k=thang*m+m+1;continue;}}for(int k=thang*m+1;k<ppos;k++){if(c[k])ans++;//计算该行不舒服度 }	} }cout<<ans<<endl;}return 0;
}