数学+贪心

    xiaoxiao2025-02-01  12

    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} ,  0ai100 . 2. The sequence is non-increasing, i.e.  a1a2...an . 3. The sum of all elements in the sequence is not zero. Professor Zhang wants to know the maximum value of  a1+a2ni=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   (2n100,0mn)  -- the length of the sequence and the number of known elements. In the next  m  lines, each contains two integers  xi  and  yi   (1xin,0yi100,xi<xi+1,yiyi+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; }

    转载请注明原文地址: https://ju.6miu.com/read-1295974.html
    最新回复(0)