Codeforces 845B Luba And The Ticket (贪心)

贪心)"/>

Codeforces 845B Luba And The Ticket (贪心)

题目链接

CF 845B

题目大意

输入六位数字，问至少改变多少个数位能使前三位的和等于后三位的和。

分析

简单的贪心。
对于初始的六位数字，我们计算前三位的和与后三位的和，接着要让每次操作都尽可能多的填补前三位和与后三位和的差距。和较小的那一组中每一位最多能弥补的差距为9减去其数位(将其变大至9)，和较大的那一组中每一位最多能弥补的差距为其数位(将其变为0)，则按6个数位最多能弥补的差距排序，从大往小尽可能填补差距，使差距小于等于0即可。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#define ls (rt<<1)
#define rs (rt<<1|1)
using namespace std;
const double pi=4*atan(1.0);
const int MAXN=100010;
const int MAXM=2*MAXN;bool cmp(int a,int b)
{return (a>b);
}
int main()
{int a[10],num1,num2,s,ans;string str;cin>>str;num1=str[0]+str[1]+str[2]-3*'0';num2=str[3]+str[4]+str[5]-3*'0';ans=0;if (num1==num2)cout<<0<<endl;else if (num1<num2){a[0]=9-(str[0]-'0');a[1]=9-(str[1]-'0');a[2]=9-(str[2]-'0');a[3]=str[3]-'0';a[4]=str[4]-'0';a[5]=str[5]-'0';sort(a,a+6,cmp);s=num2-num1;while (s>0){s-=(a[ans++]);}cout<<ans<<endl;}else if (num1>num2){a[0]=str[0]-'0';a[1]=str[1]-'0';a[2]=str[2]-'0';a[3]=9-(str[3]-'0');a[4]=9-(str[4]-'0');a[5]=9-(str[5]-'0');sort(a,a+6,cmp);s=num1-num2;while (s>0){s-=(a[ans++]);}cout<<ans<<endl;}return 0;
}
/*
651894
*/