大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。
题目大意:
n波人去k*k的电影院看电影。
要尽量往中间坐,往前坐。
直接枚举,贪心,能坐就坐,坐在离中心近期的地方。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #define maxn 1000005 #define lowbit(x) (x&(-x)) using namespace std; struct BIT { int sum; void init(){sum=0;} }bit[105][105]; int q,n; int Sum(int row,int x) { int ret=0; for(int i=x;i>=1;i-=lowbit(i)) ret+=bit[row][i].sum; return ret; } int query(int row,int l,int r) { return Sum(row,r)-Sum(row,l-1); } void update(int row,int x) { for(int i=x;i<=n;i+=lowbit(i)) bit[row][i].sum++; } int cal(int s,int e) { return (s+e)*(e-s+1)/2; } int main() { scanf("%d%d",&q,&n); int cen=n/2+1; for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) { bit[i][j].init(); } for(int i=1;i<=q;i++) { int num; scanf("%d",&num); int ansr=-1,ansc=-1; int min_val=0x3f3f3f3f; for(int r=1;r<=n;r++) { for(int c=1;c+num-1<=n;c++) { if(query(r,c,c+num-1)==0) { int tmp; if(c>=cen) { tmp=cal(c,c+num-1)-cen*num+abs(r-cen)*num; } else if(c+num-1<=cen) { tmp=cen*num-cal(c,c+num-1)+abs(r-cen)*num; } else { tmp=abs(r-cen)*num+cal(cen,c+num-1)-(c+num-cen)*cen+cen*(cen-c)-cal(c,cen-1); } if(tmp<min_val) { min_val=tmp; ansr=r; ansc=c; } } } } if(min_val!=0x3f3f3f3f) { printf("%d %d %d\n",ansr,ansc,ansc+num-1); for(int j=ansc;j<=ansc+num-1;j++) update(ansr,j); } else puts("-1"); } return 0; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118389.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...