求解滴滴俄罗斯套娃只Ac了百分之90 ，求指点错误

手写个快排。然后按宽排一次，在宽的基础上按高排一次不就行了?

A了50%的飘过= =

我是重新定义比较规则，进行排序

AC  

我也是90%，也是重新排序，但是考虑不出边界值了

我是C++，最开始也是90%，然后把长宽比较下交换了位置就AC了。

import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); int[][] toys = new int[n][2]; for (int i = 0; i < n; i++) { toys[i][0] = sc.nextInt(); toys[i][1] = sc.nextInt(); } Arrays.sort(toys, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { if (o1[0] == o2[0]) return o1[1] <= o2[1] ? -1 : 1; return o1[0] <= o2[0] ? -1 : 1; } }); int count = 1; int i = 0, j = 1; while (j <= n-1) { if (toys[j][0] > toys[i][0] && toys[j][1] > toys[i][1]) { count++; i = j; } j++; } System.out.println(count); } } } 为什么感觉我写的好low，虽然AC了。。

80%

package Unfinished; import java.util.Comparator; import java.util.Scanner; import java.util.TreeSet; /* * 直接用一个TreeSet 保存这个对象，重写一下compare方法，保证从小到大的顺序 * 再依次比较计算一下，各个对象x，y值是否递增就ok了 100% */ public class SizeMatch{ private int x ; private int y ; public SizeMatch(int x, int y) { super(); this.x = x; this.y = y; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); TreeSet<SizeMatch> set = new TreeSet<SizeMatch>(new Comparator<SizeMatch>() { @Override public int compare(SizeMatch o1, SizeMatch o2) { if(o1.x<o2.x){ return -1; }else if(o1.x>o2.x){ return 1; }else{ if(o1.y<o2.y){ return -1; }else if(o1.y>o2.y){ return 1; }else{ return 0; } } } }); for(int i=0;i<n;i++){ int x = sc.nextInt(); int y = sc.nextInt(); set.add(new SizeMatch(x, y)); } handler(set); sc.close(); } private static void handler(TreeSet<SizeMatch> set) { int result = 1; SizeMatch fisrt = set.first(); int x= fisrt.x; int y= fisrt.y; for(Object size : set.toArray()){ SizeMatch temp = (SizeMatch) size; if(x<temp.x&&y<temp.y){ result++; x = temp.x; y = temp.y; } } System.out.println(result); } }

我也来贴一个 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main(void) { int n = 0, w = 0, h = 0; cin >> n; vector<pair<int, int>> data; for (int i = 0; i < n; ++i) { cin >> w >> h; data.push_back({ w,h }); } sort(data.begin(), data.end()); vector<int> dp(n, 1); for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { if (data[i].first > data[j].first && data[i].second > data[j].second && dp[i]<dp[j]+1) { dp[i] = dp[j] + 1; } } } auto it = max_element(dp.begin(), dp.end()); cout << *it << endl; return 0; }

有前端的吗？的只通过了60%。。。

#include<stdio.h> void quickSort(int a[], int b[],int low, int high) {     int i = low, j = high, temp =a[low],temp2=b[low];     if (low > high) {         return;     }     while (i!=j)     {         while (i<j&&a[j]>=temp)         {             j--;         }         while (i<j&&a[i]<=temp)         {             i++;         }         if (i < j) {             int t = a[i];             a[i] = a[j];             a[j] = t;             t = b[i];             b[i] = b[j];             b[j] = t;         }     }     a[low]= a[i];     b[low] = b[i];     b[i] = temp2;     a[i] = temp;     quickSort(a,b ,low, i - 1);     quickSort(a, b,i + 1, high); } int main() {     int n;     int wa[1000], ha[1000];     int w, h;     scanf_s("%d", &n);     for (int i = 0; i < n; i++) {         scanf_s("%d%d", &w, &h);         wa[i]= w;         ha[i]= h;     }     quickSort(wa,ha,0, n-1);     int i = 0;     int count =1;     for (int j = i + 1; j < n; j++) {         if (wa[i] < wa[j] && ha[i] < ha[j]) {             count++;             i = j;         }     }     printf("%d\n", count); }

不是手动写个排序就过去了吗= =

NSGA-II非劣排序

AC 通过 #include <iostream> #include <string> #include <vector> #include <algorithm> #include <map> using namespace std; struct Recta { int width; int height; Recta(int _w = 0, int _h = 0) :width(_w), height(_h) {}; }; bool m_comp(const Recta& a, const Recta& b) { if (a.width == b.width) { return a.height < b.height; } else { return a.width < b.width; } } int maxCount(int number, vector<Recta> datas) { int res = 1; int outW, outH; sort(datas.begin(), datas.end(), m_comp); //按照width升序排序 outW = datas[0].width; outH = datas[0].height; for (int i = 1; i < number; i++) { if (datas[i].width > outW && datas[i].height > outH) { res++; outW = datas[i].width; outH = datas[i].height; } } return res; } int main() { int number; Recta temp; while (cin>>number) { vector<Recta> datas(number); for (int i = 0; i < number; i++) { cin >> temp.width >> temp.height; datas[i] = temp; } cout << maxCount(number,datas) << endl; } //system("pause"); return 0; }

同AC struct node {     int x,y;     bool operator<(const node& a)const     {         return x < a.x || (x == a.x && y < a.y);     } }a[55]; int n; int dp[55]; int main() { while(scanf("%d",&n) != EOF)     {         for(int i = 0; i < n; i++)             scanf("%d%d",&a[i].x,&a[i].y);         sort(a,a+n);         int ans = 0;         dp[0] = 1;         for(int i = 1; i < n; i++)         {             dp[i] = 1;             for(int j = 0; j < i; j++)                 if(a[j].x < a[i].x && a[j].y < a[i].y)                     dp[i] = max(dp[i],dp[j]+1);             ans = max(ans,dp[i]);         }         printf("%d\n",ans);     } return 0; }