It’s All In The Mind
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 146 Accepted Submission(s): 73
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:
- 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)/(a1+…+an) 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
Author
zimpha
Source
2016 Multi-University Training Contest 2
题意：
有一个由n个数组成的数字序列，其中只知道m个数（位置和值），并且这是一个单调不增的序列，且数字的最大值为100，现在想要知道(a1+a2)/(a1+…+an)这个值最大能是多少。
题解：
观察这个值就知道，要让a1,a2尽量大，其余的尽量小就可以啦。
//
// main.cpp
// 160721-1009
//
// Created by 袁子涵 on 16/7/21.
// Copyright ? 2016年 袁子涵. All rights reserved.
//#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
#include <string>using namespace std;int t,n,m,head,tail,now,fz,fm,nextmax,yue;
typedef struct
{int plz,num;
}node;
node data[105];
int cmp(node a,node b)
{return a.plz<b.plz;
}
int gcd(int a,int b)
{if (b==0)return a;return gcd(b, a%b);
}
int main(void)
{ios::sync_with_stdio(false);cin >> t;while (t--) {cin >> n >> m;for (int i=0; i<m; i++)cin >> data[i].plz >> data[i].num;head=fz=fm=0;tail=m;nextmax=100;now=1;data[tail].plz=n+1,data[tail].num=0;sort(data+0, data+m, cmp);for (int i=0; i<=m; i++) {while (now<=min(2,data[i].plz-1)) {fz+=nextmax;fm+=nextmax;now++;}if (now<=2) {fz+=data[i].num;fm+=data[i].num;}elsefm+=(data[i].plz+1-now)*data[i].num;now=data[i].plz+1;nextmax=data[i].num;}yue=gcd(fm,fz);fm/=yue;fz/=yue;cout << fz << '/' << fm << endl;}return 0;
}