| An Easy Geometry Problem |
| Description |
Lily is interested in hyperspace recently, and she is trying to solve an easy problem now. Given an n-dimensional hyperspace, assuming each dimension is a1, a2, a3, ..., an. And for each i (1 ≤ i ≤ n), j (i < j ≤ n), there is a plane ai=aj These planes have divided the hyperspace into different regions. For example, in 3D hyperspace, we have three planes: x=y, y=z and x=z. Now given q queries, for each query, there is a point (x1, x2, x3, ..., xn). Lily wants to know the maximum radius r of an n-dimensional ball she can put in point (x1, x2, x3, ..., xn), which means the center of the ball is in point (x1, x2, x3, ..., xn) and the ball’s surface cannot cross but can touch any planes mentioned above. The equation of an n-dimensional ball with center (x1, x2, x3, ..., xn) is |
| Input |
First line contains an integer T (1 ≤ T ≤ 5), represents there are T test cases. For each test case: First line contains two integers n (3 ≤ n ≤ 50000) and q (1 ≤ q ≤ 8), where n is the dimension of the hyperspace, and q is the number of queries. Following q lines, each line contains n integers x1, x2, x3, ..., xn (-109 ≤ xi ≤ 109), represents the coordinate of the ball’s center. |
| Output |
For each test case, output one line containing "Case #X:"(without quotes), where X is the case number starting from 1, and output q lines containing the maximum possible radius of the ball in each query in input order, rounded to four decimal places. |
| Sample Input |
1 3 2 0 0 0 11 22 33 |
| Sample Output |
Case #1: 0.0000 7.7782 |
. And the distance between two points (x1, x2, x3, ..., xn) and (x1', x2', x3', ..., xn') in an n-dimensional hyperspace is:
.题目分析 : 给你一个所在 n 维空间中的点，会有一些平面， 比如二维空间中的 x = y 平面，现在让你求以所给平面为圆心的半径最大的圆。
首先先考虑二维空间的情况，点到直线的公式这很容易求出来，那么扩展到 n 维空间呢，也是很好想的，任取空间中的两个坐标，投射到相应的平面上，可以计算出一个半径，现在要求所有的半径，直接暴力 n^2 ，肯定会超时，现在你就可以对所给的点进行一个排序，寻找相邻的两个点的最小结果，作为答案。
代码示例 :
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
const double num = sqrt(2);
using namespace std;
typedef long long ll;ll pre[51234];ll ab(ll x){if (x < 0) return -x;else return x;
}int main (){int t;int n, q;int cas = 1;cin >> t;while(t--){cin >> n >> q;printf("Case #%d:\n", cas++);while(q--){for(int i = 1; i <= n; i++){scanf("%lld", &pre[i]);}sort(pre+1, pre+1+n); // 这里很重要 double ans = 999999999;for(int i = 1; i < n; i++){ll d = ab(pre[i]-pre[i+1]);ans = min(ans, 1.0*d/num);}printf("%.4lf\n", round(ans*10000)/10000); } } return 0;
} I .
Aggie is faced with a sequence of tasks, each of which with a difficulty value di and an expected profit pi. For each task, Aggie must decide whether or not to complete it. As Aggie doesn’t want to waste her time on easy tasks, once she takes a task with a difficulty di, she won’t take any task whose difficulty value is less than or equal to di.
Now Aggie needs to know the largest profits that she may gain.
Input
The first line consists of one positive integer t (t ≤ 10), which denotes the number of test cases.
For each test case, the first line consists one positive integer n (n ≤ 100000), which denotes the number of tasks. The second line consists of n positive integers, d1, d2, …, dn (di ≤ 100000), which is the difficulty value of each task. The third line consists of n positive integers, p1, p2, …, pn (pi ≤ 100), which is the profit that each task may bring to Aggie.
Output
For each test case, output a single number which is the largest profits that Aggie may gain.
Sample Input
1
5
3 4 5 1 2
1 1 1 2 2
Sample Output
4
题目分析 ： 类似于LIS，也可以采取维护一个最大的和的序列，但是有一点不同的是，就是在后续插入一个值后，要讲该值后面的元素中键值大于插入的，但是和却小于插入的和的 全部删除掉， 这里用 map 来维护 。
代码示例 ：
int a[eps], b[eps];int main() {//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);int t, n;map<int, int>mp;map<int, int>::iterator it, ip, is;cin >>t;while(t--){cin >> n;for(int i = 1; i <= n; i++) scanf("%d", &a[i]);for(int i = 1; i <= n; i++) scanf("%d", &b[i]);mp.clear();mp[0] = 0;int ans = 0;for(int i = 1; i <= n; i++){if (!mp.count(a[i])) mp[a[i]] = b[i];it = mp.find(a[i]);ip = --it;int p = ip->second + b[i];it++;mp[a[i]] = max(mp[a[i]], p);for(ip = ++it; ip != mp.end(); ip++){if (ip->second <= mp[a[i]]) {is = --ip;mp.erase(++ip);ip = is;}else break;}ans = max(ans, mp[a[i]]);} printf("%d\n", ans);}return 0;
}
解法二 ： 利用 dp 的思想，维护一个最长的递增子序列，将收益视为相同困难度的情况
int a[eps], b[eps];
int dp[eps2];int main() {//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);int t, n;cin >>t;while(t--){cin >> n;for(int i = 1; i <= n; i++) scanf("%d", &a[i]);for(int i = 1; i <= n; i++) scanf("%d", &b[i]);memset(dp, inf, sizeof(dp));int len = 0;for(int i = 1; i <= n; i++){int p = lower_bound(dp, dp+len, a[i])-dp;for(int j = p; j < p+b[i]; j++){dp[j] = a[i];}len = max(len, p+b[i]);}printf("%d\n", len);}return 0;
}
