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:
- For every i∈{1,2,…,n}, 0≤ai≤100.
- The sequence is non-increasing, i.e. a1≥a2≥…≥an.
- 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;//约分并输出
}
}