分情况讨论，双指针移动（附代码）

//均分纸牌，双指针贪心 #include "pch.h" #include #include using namespace std; int main() { int n, sum = 0,count=0, num[105] = {0}; cin >> n; int tail = n, head = 1; for (int i = 1; i <= n; ++i) { cin >> num[i]; sum += num[i]; } sum /= n; while (head < tail) { while (num[head] == sum&& head < tail)head++;//等于的时候直接移动指针 while (num[tail] == sum && head < tail)tail--;//移动指针 while (num[head] > sum&& head < tail) { num[head + 1] += num[head] - sum; num[head] = sum; head++; count++; } while (num[tail] > sum&& head < tail)//大于的时候移动指针并且加1 { num[tail - 1] += num[tail] - sum; num[tail] = sum; tail--; count++; } int i = 0, j = 0,left=0,right=0; for (i = 0;; ++i)//两边都小于的时候选取需要交换次数最少的完成操作 { left += num[i + head]; if (left >= sum)break; } for (j = 0;;++j) { right += num[tail - j]; if (right >= sum)break; } if (i < j) { left -= num[head + i]; count += i ; for (int k = 1; k < i; ++k)num[k+head] = 0;//过程中的都被赋值为0 num[head+i] -= (sum - left); head++; } else { count += j; right -= num[tail - j]; for (int k = 1; k < j; ++k)num[tail - k] = 0; num[tail-j] -= (sum - right); tail -- ; } } cout << count; return 0; }