X轴上有n个点,每个点都对应有数值,你可以从任意点出发,求经过K个不同数值点的最小花费。
在两点移动的花费为两点间的距离。
如果无法经过K个不同数值点,输出 “-1”.
第一行输入两个整数 n,k,
接下来有n行,每行两个数x,y 分别表示属于数值和坐标
接下来有n行,每行两个数x,y 分别表示属于数值和坐标
7,3,[[0,1],[0,2],[1,5],[1,1],[0,7],[2,8],[1,3]]
3
坐标点5出发,经过7、8两个点就经过了3个不同的数值。
所需代价 (7-5)+(8-7) = 3
其中 1<=n<=10^6, 1<=k<=50
0<=x<k, 0<=y<=1e9
#include <unordered_map> class Solution { public: /** * * @param n int整型 * @param k int整型 * @param card int整型vector<vector<>> * @return int整型 */ int solve(int n, int k, vector<vector<int> >& card) { int r = INT_MAX; sort(card.begin(), card.end(), [](vector<int>& a, vector<int>& b){return a[1]<b[1];}); unordered_map<int, int> M; for(int i=0,j=0;j<n;j++){ M[card[j][0]]++; while(i<j && M.size()==k){ r = min(r, card[j][1]-card[i][1]); if(--M[card[i][0]] == 0) M.erase(card[i][0]); i++; } } return r==INT_MAX?-1:r; } };
public int solve (int n, int k, int[][] card) { // write code here Arrays.sort(card, (c1,c2)->c1[1]-c2[1]); int INF = Integer.MAX_VALUE; int left = 0; int count = 0; int[] freq = new int[k+1]; int res = INF; for (int right = 0; right < n; right++) { if (freq[card[right][0]] == 0) { count++; } freq[card[right][0]]++; while(left<=right && count == k){ res = Math.min(res, card[right][1] - card[left][1]); freq[card[left][0]]--; if (freq[card[left][0]]==0) { count--; } left++; } } if (res == INF) { return -1; } return res; }
bool cmp(vector<int> & a, vector<int> & b){ return a[1] < b[1]; } class Solution { public: /** * * @param n int整型 * @param k int整型 * @param card int整型vector<vector<>> * @return int整型 */ int solve(int n, int k, vector<vector<int> >& card) { // write code here const int N = card.size(); sort(card.begin(), card.end(), cmp); vector<int> cnt(k,0); int seem = 0; int left = 0; int ans = INT32_MAX; for( auto c : card){ cnt[c[0]] ++; if(cnt[c[0]] == 1){ seem++; } if(seem == k){ ans = min(ans, c[1] - card[left][1]); while(left<N && cnt[card[left][0]] > 1){ cnt[card[left][0]] --; left++; ans = min(ans, c[1] - card[left][1]); } } } return (seem == k? ans : -1); } };