1477.
等值拉面
时间限制 1000 ms
内存限制 128 MB
话说Dennis的拉面馆隆重开张后,由于厨师手艺还未达到炉火纯青的地步,每碗拉面的重量并不都全部相等,故Dennis每天需亲自出马调节。
不过Dennis的拉面十分特殊,每碗都分成上下两部分,每部分的拉面重量均在1至6之间,且是整数,例如:现有排成行的4碗拉面
第一碗,上部分拉面重量为6,下部分拉面重量为1;
第二碗,上部分拉面重量为1,下部分拉面重量为5;
第三碗,上部分拉面重量为1,下部分拉面重量为3;
第四碗,上部分拉面重量为1,下部分拉面重量为2;
所有拉面上部分的重量之和为sum-up=6+1+1+1=9,下部分的数量之和为sum-down=1+5+3+2=11。这4碗拉面的上下数量之差的绝对值为11-9=2。
但是Dennis的每碗拉面上下可以互换,但只限于同一碗拉面,交换一次成为一次操作。请你帮助Dennis用最少的操作次数使给出的n份拉面的上下数量之差的绝对值最小。
例如这以上的4碗拉面,只需将第四碗拉面的上下部分交换,便可使上下部分之差为0。
输入数据
输出数据
样例输入
复制
4
6 1
1 5
1 3
1 2
\n
· \n
· \n
· \n
· \n
样例说明
30%的数据,n< =15
100%的数据,n< =1000