MYF

HDU 5742 It's All In The Mind

Posted on | In | | Visitors

题目链接

HDU 5742

题目分析

题目大意

n个数字，有的知道有的不知道，求(a1+a2)/(a1+a2+…+an)的最大值。

解析

想要该分式值最大，只需要让上面的值尽可能大，下面的值尽可能小即可。所以先判断a1,a2是否已知，如果都知道，则找后面的数字，后面的数字要尽可能的贴近靠右的已知的那个值。所以我们从右往左处理，将未知的值更新为他右侧第一个已知的值，求一下gcd约分即可。

代码

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
59
60
61
62
63
64
65
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define mp make_pair
#define pb push_back
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const int maxn=100000+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int main(){
    int t;
    int a[105],n,m,pos,val;
    scanf("%d",&t);
    while (t--) {
        scanf("%d%d",&n,&m);
        Memset(a, -1);
        for (int i=1; i<=m; i++) {
            scanf("%d%d",&pos,&val);
            a[pos]=val;
        }
        if (a[1]==-1) {
            a[1]=100;
        }
        if (a[2]==-1) {
            a[2]=a[1];
        }
        
        int tmp=0;
        for (int i=n; i>=1; i--) {
            if (a[i]!=-1) {
                tmp=a[i];
            }
            else{
                a[i]=tmp;
            }
        }
        int sum=0,fz=a[1]+a[2];
        for (int i=1; i<=n; i++) {
            sum+=a[i];
        }
        int gcd=__gcd(sum,fz);
        cout<<fz/gcd<<"/"<<sum/gcd<<endl;
    }
}