It’s All In The Mind

<mark>Problem Description</mark>
Professor Zhang has a number sequence a1,a2,…,an. However, the sequence is not complete and some elements are missing. Fortunately, Professor Zhang remembers some properties of the sequence:

  1. For every i∈{1,2,…,n}, 0≤ai≤100.
  2. The sequence is non-increasing, i.e. a1≥a2≥…≥an.
  3. The sum of all elements in the sequence is not zero.

Professor Zhang wants to know the maximum value of a1+a2∑ni=1ai among all the possible sequences.
<mark>Input</mark>
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first contains two integers n and m (2≤n≤100,0≤m≤n) – the length of the sequence and the number of known elements.

In the next m lines, each contains two integers xi and yi (1≤xi≤n,0≤yi≤100,xi<xi+1,yi≥yi+1), indicating that axi=yi.

<mark>Output</mark>
For each test case, output the answer as an irreducible fraction “p/q”, where p, q are integers, q>0.
<mark>Sample Input</mark>
2
2 0
3 1
3 1
<mark>Sample Output</mark>
1/1
200/201
<mark>题意</mark>
张教授有一个序列号a1,a2,…,an。但是,序列不完整,一些元素丢失。幸运的是,张教授记得序列的一些性质:

1。对于每一个i 1,2,…,n,0≤ai≤100。

2。序列不递增,即a1≥a2≥…≥an。

3。序列中所有元素的和不是零。

张教授想知道所有可能的序列中a1+a2∑ni=1ai的最大值。
输入
有多个测试用例。输入的第一行包含一个整数t,表示测试用例的数量。对于每个测试用例:

第一个包含两个整数n和m(2≤n≤100,0≤m≤n)——序列的长度和已知元素的数量。

在下一条M线中,每一个包含两个整数Xi和Yi(1×Xi<n,0±Yi<100,XiXi+1,Yi±Yi+1),表示AXI=Yi。
输出
对于每个测试用例,输出一个不可约分数“p/q”,其中p,q是整数,q>0。
这道题属于签到题难度,我们需要根据贪心思想去构造一个数组,然后进行加和计算,最后输出时要注意 输出最简分数,直接一个gcd就好了;

AC代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
bool is_positive( int m )
{
    return m > 0 ;
}

int __gcd( int m, int n )//gcd求最小公约数,,库函数中有__gcd但是笔者交题时OJ 不支持
{
    if( !is_positive(m) || !is_positive(n) )    return -1;
    int r = m % n;
    if( 0 == r ) return n;
    else return __gcd( n, r );
}

int main()
{
    int t, m, n, x, y, a[10005];//a是我们需要构造的数组(贪心思想)
    cin >> t;
    while(t--)
    {
        cin >> m >> n;
        int sum = 0;
        memset(a, -1, sizeof(a));//每次都要对数组进行初始化为-1;
        for(int i = 0; i < n; i++)
        {
            cin >> x >> y;
            a[x] = y;
        }
// for(int i =1; i <= m; i++)
// cout << a[i] << " ";
       // cout << endl;
        int flag = 0;
        for(int i = m; i >= 3; i--)//贪心思想构造数组
        {
            if(a[i] == -1)
                a[i] = flag;
            else
                flag = a[i];
            sum += a[i];
        }
        flag = 100;
        for(int i = 1; i <= 2; i++)
        {
            if(a[i] == -1)
                a[i] = flag;
            else
                flag = a[i];
            sum += a[i];
        }
// for(int i = 1; i <= m; i++)
// cout << a[i] << " ";
        //cout << endl;
        int g = __gcd(sum, a[1] + a[2]);
        cout << (a[1] + a[2]) / g << '/' << sum / g << endl;//约分并输出

    }
}

原创转载请注明出处