LeetCodeWeeklyContest-180

数据范围很小，可以直接暴力

class Solution {
public:vector<int> luckyNumbers (vector<vector<int>>& matrix) {vector<int> res;int m = matrix.size(),n= matrix[0].size();for(int i=0;i<m;i++){for(int j=0;j<n;j++){int t = matrix[i][j],flag=0;for(int k=0;k<n;k++){if(k==j) continue;if(matrix[i][k]<t) {flag =1;break;}}if(flag) continue;for(int k=0;k<m;k++){if(k==i) continue;if(matrix[k][j]>t) {flag =1;break;}}if(!flag) res.push_back(matrix[i][j]);}}return res;}
};

其实这个题，说来也简单，但是不知道为啥周赛的时候，死活过不去…
直接用一个数组来维护一个栈即可

class CustomStack {
public:int arr[10005];int msize,top=0;CustomStack(int maxSize):msize(maxSize){}void push(int x) {if(top<msize){arr[top++] = x;}}int pop() {if(top>0) return arr[--top];else return -1;}void increment(int k, int val) {for(int i=0;i<min(top,k);i++){arr[i] += val;}}
};/*** Your CustomStack object will be instantiated and called as such:* CustomStack* obj = new CustomStack(maxSize);* obj->push(x);* int param_2 = obj->pop();* obj->increment(k,val);*/

这个确实不会
思路是首先利用二叉搜索树的特点，其中序遍历是递增序列，然后再去二分这个序列，这样就可以平衡了
按照正确的思路写的，但是自己写出来会超时，后来发现，build函数nums数组忘了加引用，加了引用之后就过了，原来引用用处这么大…,原谅我的无知…

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:void dfs(TreeNode* root,vector<int>&nums){  // 加引用if(root==NULL) return ;dfs(root->left,nums);nums.push_back(root->val);dfs(root->right,nums);}TreeNode* build(vector<int>& nums,int l,int r){if(l>r) return NULL;// int mid = (l+r)>>1;int mid = l+(r-l)/2;TreeNode* root = new TreeNode(nums[mid]);root->left = build(nums,l,mid-1);root->right = build(nums,mid+1,r);return root;}TreeNode* balanceBST(TreeNode* root) {if(root==NULL) return NULL;vector<int> nums;dfs(root,nums);return build(nums,0,nums.size()-1);}
};

周赛时写了个背包，然后想都不用想会超时…
这个题的思路是按照效率降序排序，为啥要对效率排序而非速度排序，个人感觉是因为效率对表现值贡献值更大（乘法），而速度是加法。然后再找到一个速度最大的几个（不超过k个），不一定k个才最大，用一个multiset来维护速度的集合，及时更新。
参考： 效率优先，速度跟上 (C++ 贪心)

typedef long long ll;
const ll mod = 1e9+7;
bool cmp(pair<ll,ll>a,pair<ll,ll>b){if(a.first==b.first) return a.second > b.second;else return a.first > b.first;}
class Solution {
public:int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {vector<pair<ll,ll>> v;for(int i=0;i<n;i++){v.push_back(make_pair((ll)efficiency[i],(ll)speed[i]));}sort(v.begin(),v.end(),cmp);multiset<int> sp;  // 要用multisetll res = 0,spsum=0;for(int i=0;i<n;i++){if(i<k){sp.insert(v[i].second);spsum += v[i].second;}else{if(v[i].second>*sp.begin()){spsum += v[i].second-*sp.begin();sp.erase(sp.begin());sp.insert(v[i].second);}}res = max(res,spsum*v[i].first); // 由于按照效率降序排序，所以下标所指出即为当前最小值}return res%mod;}
};