MYF

HDU 5353 Average

Posted on | In | | Visitors

题目链接

HDU 5353

解题方法：枚举第一位的情况遍历环。

题目分析

题目大意

n个人，每个人各有一定数量的糖，相邻的两个人x和y只能进行一次如下三种操作的一种

  • x给y一颗糖
  • y给x一颗糖
  • x和y谁都不给谁糖

问，最终怎样操作，能使每个人的糖数相同。

解析

先判断能否平分

  1. 如果所有糖数无法整除人数则不行
  2. 每个人拥有的糖数和平均值差大于等于2时不行，因为一个人只能从左边要一颗糖，右边要一颗糖，所以一个人最多只能获得两颗糖，同理，每个人也只能给出两颗糖

处理一下，找到每个人和平均值的相对差，将这些数都凑成0。

枚举最初的状态，最初的状态只能为0, 1, -1，最终状态应该与最初状态相同，并且每次cur必须在(-2, 2)区间内，因为如果等于二了，就无法凑成0了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int n;
int a[maxn];
vector<int> x,y;
bool work(int cur){ // cur表示最初从几开始，可选为0,1,-1
    int tmp=cur;
    x.clear();
    y.clear();
    
    if (cur==1) {
        // 从n借给1一个，最后应该剩余1
        x.push_back(n);
        y.push_back(1);
    }
    else if (cur==-1) {
        // 从1借给n一个，最后应该剩余-1
        x.push_back(1);
        y.push_back(n);
    }
    
    // 遍历1~n-1
    for (int i=1; i<n; i++) {
        cur+=a[i];
        
        if (cur>=2||cur<=-2)
            return false;
        
        if (cur>0) {
            x.push_back(i);
            y.push_back(i+1);
        }
        else if (cur<0){
            x.push_back(i+1);
            y.push_back(i);
        }
    }
    
    // 判断n个加在一起是否是tmp 即最初的状态
    if (cur+a[n]!=tmp)
        return false;
    else
        return true;
}
void output(){
    puts("YES");
    int sz=x.size();
    printf("%d\n",sz);
    for (int i=0; i<sz; i++) {
        printf("%d %d\n",x[i],y[i]);
    }
}
int main(){
    int t;
    scanf("%d",&t);
    while (t--) {
        int mx=-1,mn=INF;
        ll sum=0,ave;
        scanf("%d",&n);
        for (int i=1; i<=n; i++) {
            scanf("%d",&a[i]);
            mx=max(mx, a[i]);
            mn=min(mn, a[i]);
            sum+=a[i];
        }
        
        // 无法整除
        if (sum%n) {
            puts("NO");
            continue;
        }
        
        // 浮动大于2
        ave=sum/n;
        if (mx-ave>2||ave-mn>2) {
            puts("NO");
            continue;
        }
        
        // 处理一下
        for (int i=1; i<=n; i++)
            a[i]-=ave;
        
        if (work(0))
            output();
        else if (work(-1))
            output();
        else if (work(1))
            output();
        else
            puts("NO");
    }
}