Unfair Poll

题意:一共有n排同学每排同学有m个人, 老师问问题有一个顺序, 先从第一排开始问,问完第一排的所有同学之后,再问第2排的,对于所有排的访问顺序为 1,2,3……n-1,n,n-1,n-2,……,2,1,2,然后每次访问到新的一排先要问完这一排的所有人才会往下一(目标)排走。

题解:先声明我们开一个数组来记录这一排被询问的总次数,先将k  /= m, 这个代表的是完全访问的次数,即一整排m位同学都问完有几次,如果  完全访问的次数< n, 我们就将前几排全访问次数的人都加上m,并且将剩下的访问次数都塞到一下排就好了,如果完全访问次数大于n了之后,发现除了第一次转移的次数位n-1排, 我们再对 k/=(n-1) 处理出来, 然后判断奇偶性来决定最后一次是从上到下还是从下到上,对于所有的排都加上次数,最后再把刚开始的访问次数塞到目标排就好了。

n==1的话,对于上述解法要特殊讨论因为除数或者模数不能为0。

代码:

 #include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = (int)1e9+;
const int N = 2e5 + ;
LL n, m, x, y;
LL k, ans1, ans2 = INF, ans3;
LL cnt[N];
int main(){
scanf("%I64d%I64d%I64d%I64d%I64d", &n, &m, &k, &x, &y);
LL c1, c2;
c1 = k/m;
c2 = k%m;
swap(c1, k);
if(k < n){
for(int i = ; i <= k; i++) cnt[i] = m;
cnt[k+] = c2;
}
else {
for(int i = ; i <= n; i++) cnt[i] = m;
k -= n;
if(n != ){
LL t = n-;
LL z = k / t;
LL lf = k % t;
LL t1 = z-z/;
for(int i = ; i < n; i++) cnt[i] += t1*m;
for(int i = ; i <= n; i++) cnt[i] += z/ * m;
if(z&1ll){
int g = ;
for(int i = ; i <= n, lf > ; i++, lf--) cnt[i] += m, g = i;
cnt[++g] += c2;
}
else{
int g = n;
for(int i = n-; i >= , lf > ; i--, lf--) cnt[i] += m, g = i;
cnt[--g] += c2;
}
}
else cnt[] = c1;
}
for(int i = ; i <= n; i++){
if(cnt[i] == ) {ans2 = ; continue;}
if(i == x) {
LL lf = cnt[i]%m;
ans3 = cnt[i]/m;
if(lf >= y) ans3++;
};
LL t1 = cnt[i]/m;
if(cnt[i]%m) t1++;
ans1 = max(ans1, t1);
LL t2 = cnt[i]/m;
ans2 = min(ans2, t2);
} printf("%I64d %I64d %I64d", ans1, ans2, ans3);
return ;
}

758 C

05-20 09:53