2017 CCPC 中南地区邀请赛 E Strange Optimization

发表于 | 分类于 | 阅读次数:
字数统计: 549 字

题目链接：http://202.197.224.59/OnlineJudge2/index.php/Contest/read_problem/cid/43/pid/1268

题意

定义一个函数：f(t)=min(i,j∈ℤ)|i/n−j/m+t|，给出n和m，求使得f(t)最大的t的取值。（式子可以查看原网页中的式子）

题解

因为i,j都是可以取任意整数的，所以进行式子中的前两个部分进行通分以后就是(im-jn)/mn。
观察我们可以得到要得到最大值t的值就是上述式子的最小精度的一半，求最小精度就是要求分子(im-jn)能表示的数的间隔
这个间隔我用一个比较巧妙的方法求得，用一个优先队列来存放这两个数，不断从优先队列中取出两个最小的数做差，然后再放入优先队列中，直到取出的这两个最小的数是相同的。
最后对得到的分数进行化简就是最后的答案了

代码

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

#define INF 0x3f3f3f3f
typedef long long ll;
const int maxn=15;

ll gcd(ll a,ll b)
{
	return b==0?a:gcd(b,a%b);
}

ll llc(ll a,ll b)
{
	return a*b/gcd(a,b);
}

void solve()
{
	ll n,m;
	while(cin>>n>>m)
	{
		priority_queue<ll,vector<int>,greater<int> > Q;
		Q.push(n);
		Q.push(m);
		ll s1,s2,tmp;
		s1=Q.top(),Q.pop(),s2=Q.top(),Q.pop();
		while(s1!=s2)
		{
			//cout<<s1<<s2<<endl;
			tmp=abs(s1-s2);
			Q.push(s1),Q.push(s2),Q.push(tmp);
            s1=Q.top(),Q.pop(),s2=Q.top(),Q.pop();
		}
		ll p=s1,q=2*m*n;
		tmp=gcd(p,q);
		while(tmp!=1)
		{
			p/=tmp,q/=tmp;
			tmp=gcd(p,q);
		}
		cout<<p<<"/"<<q<<endl;
	}
}

int main()
{
	freopen("input.txt","r",stdin);
	solve();
	return 0;
}

小结

做出这道题的时候还是有些激动的，因为在现场赛上两题如果罚时不多的话就是铜牌。哈哈，如果我去打这场比赛就能够拿一个铜牌。
好好努力，提升实力，以后在区域赛上拿牌就美滋滋了。