【第一道感悟到数学思维力量的题】A. Luntik and Concerts

题目来源：Problem - A - Codeforces​​​​​​https://codeforces.com/contest/1582/problem/A

题干：

 第一组测试数据：

本人TLE源代码：

#include
#include
#include
#include
#include
#include
#include
#define PI 3.1415927
using namespace std;int main()
{std::ios::sync_with_stdio(false);int t;cin >> t;while (t--){long long int a, b, c;long long int sum1 = 0, sum2 = 0;long long int count = 100000000;cin >> a >> b >> c;for (long long int i = 0; i <= a; i++)for (long long int j = 0; j <= b; j++)for (long long int k = 0; k <= c; k++){sum1 += i + 2 * j + 3 * k;sum2 += (a - i) + 2 * (b - j) + 3 * (c - k);if (fabs(sum1 - sum2) < count)count = fabs(sum1 - sum2);sum1 = 0;sum2 = 0;}cout << count << endl;}return 0;
}

TLE原因：贪婪算法，将每一种可能的组合尝试，当a,b,c过大的时候运算时间过大

官方思路：

用贪婪算法，易证： 

包括数学归纳法，假设N<=S，上式成立

将a+1,b+1，c+1的情形进行讨论（不是数学专业，证明过程不赘述）

因此当S为偶数时，总能得到n1,n2,n3使得S/2=n1+2n2+3n3;

所以第一场则为s/2，第二场为s-s/2=s/2;

fabs(s1-s2)=0;

当S为奇数时，总能得到n1,n2,n3,使得[S/2]=n1+2n2+3n3;(取整函数）

因此fabs(s1-s2)=1;

又因为s=a+2b+3c;

2b+2c为偶数，则为了减少运算量，只需讨论a+c奇偶性即可；

官方源代码：

#includeusing namespace std;main() {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t, a, b, c;cin >> t;while (t--) {cin >> a >> b >> c;cout << (a + c) % 2 << '\n';}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！