Problem Description 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. Input 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 . Output For each test case, output the answer as an irreducible fraction " p / q ", where p , q are integers, q>0 . Sample Input
2 2 0 3 1 3 1 Sample Output 1/1 200/201
题意：
有一个长为n的不增序列，给出序列中的部分值，求(a1+a2)/sum的最大值。
分析：
很显然的贪心，只要让a1,a2尽可能的大，让剩下的数尽可能的小即可。
代码：
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<cstdlib> #include<ctime> #include<vector> #include<queue> #include<stack> #include<map> #include<set> #include<algorithm> using namespace std; int a[110]; int main() { int t ; cin >> t; while(t--) { memset(a,-1,sizeof(a)); int n,m; cin >> n >> m ; for(int i = 0 ; i < m ; i ++) { int pos,data; scanf("%d%d",&pos,&data); a[pos] = data; } //长度是n; int top = 0; for(int i = n ; i >= 3 ; i --) { if(a[i] == -1) a[i] = top; else top = a[i]; } if(a[2] == -1) { if(a[1] == -1) a[2] = 100; else a[2] = a[1]; } if(a[1] == -1) a[1] = 100; int fz,fm; fz = fm = 0; for(int i = 1 ; i <= n ; i ++) fm += a[i]; fz = a[1] + a[2]; int gcd = __gcd(fz,fm); printf("%d/%d\n",fz/gcd,fm/gcd); } return 0; }
