赞
踩
T1:处理用时最长的那个任务的员工
这个题目最开始可能会想到哈希表的做法。但是需要注意的是,会有同一个工号做了不止一种任务,所以在哈希表存储的过程中会覆盖掉这个工号之前的记录,导致无法正确找到最大长时间。
所以就老老实实遍历更新最大值就好了。
class Solution { public: int hardestWorker(int n, vector<vector<int>>& logs) { vector<int> a; a.push_back(logs[0][1]); for(int i = 1 ; i < logs.size() ; i ++) { int w = logs[i][1] - logs[i - 1][1]; a.push_back(w); } int m = 0; int p= 0; for(int i = 0 ; i < logs.size() ; i ++) { if(a[i] > m) { m = a[i]; p = logs[i][0]; } else if(a[i] == m) { p = min(p , logs[i][0]); } } return p ; } };
T2:找出前缀异或的原始数组
这个题目写不出来就在于不了解异或的一些特性。
*按位异或的3个特点:
(1) 00=0,01=1 0异或任何数=任何数
(2) 10=1,11=0 1异或任何数-任何数取反
(3) 任何数异或自己=把自己置0*
变形可知:
对于x ^ y = z,
知道x与z求y 两边同时^x即可:x ^ y ^ x = z ^ x = y ^ 0 = y
由题意可知:
pref[1] = arr[0] ^ arr[1];
pref[2] = arr[0] ^arr[1] ^ arr[2];
…
利用异或的第三条特点可知:
arr[1] = arr[0] ^ pref[1];
arr[2] = arr[0] ^arr[1] ^pref[2];
又arr[1] = arr[0] ^ pref[1];
=> arr[2] = pref[1] ^ pref[2];
…
由此得到arr[i] 的递推式。
class Solution {
public:
vector<int> findArray(vector<int>& pref) {
vector<int> arr(pref.size());
arr[0] = pref[0];
for(int i = 1 ;i < pref.size() ; i++){
arr[i] = pref[i - 1] ^ pref[i];
}
return arr;
}
};
acwing:
T1:最小值
这个题目的思路就非常的简单明了。
#include <iostream> #include <cstring> #include <algorithm> using namespace std; int main(){ int t ; cin >> t ; while(t--){ int a , b; cin >> a >> b; int res = min(a , (a+b)/3); int c = min(res , b); cout << c << endl; } }
T2:压缩文件
这个题目可能会绕进去的点在于觉得需要记录每个文件的下标(当然可能只有我)。其实思路也是很明了的了。
第一步看是否有必要压缩,如果文件需要的空间比优盘空间小,就没必要压缩。
第二步就是将文件压缩前后的差值按由大到小排序(因为要压缩次数最少,所以压缩一次就尽可能得到更大的空间)然后看需要减去几次差值满足要求即可。
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 100010; int n , m ; int w[N]; int main(){ cin >> n >> m; long long sum; for(int i = 0 ;i < n ;i ++){ int a , b ; cin >> a >> b; sum += a; w[i] = a - b; } sort(w , w+n , greater<int>()); if(sum <= m) cout << "0" << endl; else{ for(int i = 0 ;i < n ; i++){ sum -= w[i]; if(sum <= m){ cout << i + 1 << endl; return 0; } } cout << "-1" << endl; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。