来源：967 质量检测
大意：n 种 商品有 a、b 两种分数，确定一种分数，大于等于 maxScore*p 分数的商品可被取到，求最多能取到的商品
吐槽
从天池居然看到了周赛（我还疑心阿里怎么也办起算法比赛来啦，原来是和九章合作的 lintcode 周赛，只是同步到天池而已），饶有兴趣了选了一道3星题，读完就是一个字：迷惑，好像有点难又好像很简单。半小时后，我决定要看题解，因为我真的有些读不懂题意，但是天池周赛没有题解，别人提交的代码不能看（或许是我没参加笔试，闲人免进？），我赶紧 google 起来，结果没有任何有效搜索！想起周赛上带的标签--九章算法出品，和 lintcode 合作，于是我立马在 lintcode 官网查询起来，结果大失所望，题目倒是有，但是题解呢？没有？官网提交的代码不能查看--要 VIP，一月 30 美刀的开销实在是。。。毕竟是 leetcode vip 的 N 倍。讨论区空无一人，和热闹非凡的 leetcode 简直天壤之别。然后尝试在 github 摸索一番也是毫无所获。所幸在 lintcode 笔记看到破解的蛛丝马迹，一番折腾之后，终于 AC.思路 & 代码
思路：因为必须先确定商品最大分数，才能进行“可获取商品”的计算，注意到每种商品分数有两种，所以在将商品分数合在一起排序后，用 num 数组记录选择商品的次数（避免重复计算），同时用 occur 数组记录选择范围内的商品重复次数（每轮选择的最大分数必须是在所有商品都被选择的前提下），滑动窗口从后往前维护即可（hi 确定当前最大分数，lo 确定满足分数界限的最低值）！时间：O(nlogn)，空间：O(n)
public class Solution {
/**
* @param a: the excellent scores
* @param b: the good scores
* @param p: p% stands the line of valuable products.
* @return: return the possible max number products to buy.
*/
public int qualityInspection(int[] a, int[] b, int p) {
// write your code here
int n = a.length;
Commodity[] commodity = new Commodity[2*n];
for(int i = 0; i < n; i++) {
commodity[2*i] = new Commodity(a[i], i);
commodity[2*i+1] = new Commodity(b[i], i);
}
Arrays.sort(commodity, (o1, o2) -> { // 排序，注意写法！！！
if(o1.score < o2.score) return -1;
return 1;
});
int[] num = new int[n]; // 商品被选择的次数（0、1、2）
int[] occur = new int[n]; // 商品重复次数（用于确定最大分数）
for(int i = 0; i < n; i++) occur[i] = 2;
int ans = 0, cur = 0;
int lo = 2*n-1, hi = 2*n-1;
while(true) {
while(lo >= 0 && commodity[lo].score >= (float)(commodity[hi].score*p)/100) {
if(num[commodity[lo].index] == 0) cur++; // 商品第一次被选择
num[commodity[lo--].index]++;
}
ans = Math.max(ans, cur);
if(lo < 0) break;
while(hi > lo && commodity[lo].score < (float)(commodity[hi].score*p)/100) {
if(occur[commodity[hi].index] == 2) {
if(num[commodity[hi].index] == 1) cur--;
num[commodity[hi].index]--;
occur[commodity[hi--].index]--;
} else { // 1 （每个商品都会参与最大分数的比较，所以不能为0）
return ans;
}
}
}
return ans;
}
}
class Commodity {
int score;
int index;
Commodity(int score, int index) {
this.score = score;
this.index = index;
}
}