codeforces 845B.Luba And The Ticket"/>
codeforces 845B.Luba And The Ticket
题目大意:
有一串6位数的数字,每个数字可以变换成任意数字(0-9),变换最小个数数字使这串数字成为一个lucky数。
所谓lucky即这个6位数的前三位数字和与后三位数字和相等。
比较简单的贪心。
每个数字可以增大或减小,这个数字是可以算出来的,要想变换次数最小,就优先变换这个最大数值。
举个栗子:777651 每个数字上升范围是222348 下降范围是777651
看前三个数减后三个数的差 如果为正 则前三个数的下降即后三个数的上升中选择,反之则在前三个数的下降和后三个数的上升中选择。
(7+7+7)-(6+5+1) = 9 > 0 则前三个数应该减小,后三个数增大 这样才能达到lucky状态
即在777348中选最大的 第一次选到8 第二次选到7 两次即可变换成功。
其实很容易发现最多只需变换3次,将前3个数变成后3个数。
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
int s[6],b[6];
int p[6],v[6];
bool cmp( int a, int b )
{return a>b;
}
int main()
{string str;cin >> str;for ( int i = 0 ; i < 6 ; ++ i ){s[i] = (str[i]-'0');b[i] = 9-s[i];}int s1 = 0, s2 = 0;for ( int i = 0 ; i < 3 ; ++ i ){s1 += s[i];s2 += s[i+3];p[i] = s[i];p[i+3] = b[i+3];v[i] = b[i];v[i+3] = s[i+3];}int sub = s1-s2;if ( s1 == s2 ) puts( "0" );else if ( sub > 0 ) // 前大 {int cnt = 0;while( sub > 0 ){sort( p, p+6, cmp );sub-=p[0];p[0] = 0;cnt ++;}printf( "%d", cnt );}else {int cnt = 0;while( sub < 0 ){sort( v, v+6, cmp );sub+=v[0];v[0] = 0;cnt ++;}printf( "%d", cnt );}return 0;
}
更多推荐
codeforces 845B.Luba And The Ticket
发布评论