【注意:本题按通过的Case比例给分】
给定N个矩形,每个矩形宽W米高H米
请按以下规则将这N个矩形排序,输出排序后的矩形列表排序规则:
面积小的矩形排在面积大的矩形前面
面积相同的矩形,按照宽高比排序,宽高比大的矩形排在宽高比小的矩形前面
宽高比的定义为 min(W/H, H/W)
面积和宽高比都相同的矩形,按照宽排序,宽度更小的矩形排在宽度更大的矩形前面
每组输入两行输入
第一行是一个整数N (0 < N <= 100)
第二行是2*N个整数,分别是每个矩形的宽W和高H,(0 < W,H <= 100)
每组数据输出一行,2*N个整数,分别是排序后的每个矩形的宽W和高H
2 2 2 1 1
1 1 2 2
#include <bits/stdc++.h> using namespace std; #define INF 1e-9 struct node { int w, h; }; bool cmp(node a, node b) { if (a.w * a.h < b.w * b.h) return true; else if (a.w * a.h > b.w * b.h) return false; else { double wa = a.w, ha = a.h, wb = b.w, hb = b.h; double v1 = min(wa / ha, ha / wa); double v2 = min(wb / hb, hb / wb); if (v1 - v2 < -INF) return false; else if (v1 - v2 > INF) return true; else { if (a.w < b.w) return true; else return false; } } } int main() { int n; scanf("%d", &n); vector<node> res(n); for (int i = 0; i < n; ++i) { scanf("%d%d", &res[i].w, &res[i].h); } sort(res.begin(), res.end(), cmp); for (int i = 0; i < n; ++i) { i == n - 1 ? printf("%d %d\n", res[i].w, res[i].h) : printf("%d %d ", res[i].w, res[i].h); } return 0; }
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] w = new int[2*n]; for (int i = 0; i <2*n ; i++) { w[i] = sc.nextInt(); } for (int i = 0; i <2*n ; i+=2) { for (int j = i+2; j <2*n ; j+=2) { if(w[j]*w[j+1]<w[i]*w[i+1]){ swap(w,j,i); swap(w,j+1,i+1); }else if ((w[j]*w[j+1]==w[i]*w[i+1])&&(Math.min(w[j]/w[j+1],w[j+1]/w[j])>Math.min(w[i]/w[i+1],w[i+1]/w[i]))){ swap(w,j,i); swap(w,j+1,i+1); }else if ((w[j]*w[j+1]==w[i]*w[i+1])&&(Math.min(w[j]/w[j+1],w[j+1]/w[j])==Math.min(w[i]/w[i+1],w[i+1]/w[i]))&&w[j]<w[i]){ swap(w,j,i); swap(w,j+1,i+1); } } } for (int i = 0; i < 2*n ; i++) { if(i!=2*n-1) { System.out.print(w[i] + " "); }else { System.out.print(w[i]); } } } public static void swap(int[] arr,int i,int j){ int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } }
#include <iostream> #include <vector> #include <algorithm> #include <utility> using namespace std; bool cmp1(pair<int, int>a, pair<int, int>b) {//根据面积排序 return a.first*a.second < b.first*b.second; } bool cmp2(pair<int, int>a, pair<int, int>b) {//根据宽高比排序 int t1 = a.first, t2 = a.second, t3 = b.first, t4 = b.second; if (t1 > t2) swap(t1, t2); if (t3 > t4) swap(t3, t4); return t1 * t4 > t3 * t2; } bool cmp3(pair<int, int>a, pair<int, int>b) {//根据宽度排序 return a.first < b.first; } int main() { int N; pair<int, int>matrix; vector<pair<int, int>>que; cin >> N; for (int i = 0; i < N; ++i) { cin >> matrix.first >> matrix.second; que.push_back(matrix); } stable_sort(que.begin(), que.end(), cmp3);//sort会改变元素的相对位置 stable_sort(que.begin(), que.end(), cmp2); stable_sort(que.begin(), que.end(), cmp1); for (int i = 0; i < N; ++i) { cout << que[i].first << ' ' << que[i].second << ' '; } return 0; }
#include <iostream> #include <vector> #include <algorithm> using namespace std; int comp(vector<double> a, vector<double> b){ if(a[0] * a[1] < b[0] * b[1]) return 1; else if (a[0] * a[1] > b[0] * b[1]) return 0; else{ if(min(a[0]/a[1],a[1]/a[0]) > min(b[0]/b[1],b[1]/b[0])) return 1; else if (min(a[0]/a[1],a[1]/a[0]) < min(b[0]/b[1],b[1]/b[0])) return 0; else{ if(a[0] < b[0]) return 1; else return 0; } } } int main(void) { int n; cin>>n; vector<vector<double>> nums(n,vector<double>(2,0)); for(int i=0;i<n;i++){ cin>>nums[i][0]>>nums[i][1]; } sort(nums.begin(),nums.end(),comp); for(auto i:nums){ cout<<i[0]<<' '<<i[1]<<' '; } return 0; }
重写cmp方法,对两个PII类型变量比大小。用PII类型存储长方形的宽和高。最后重写一个快速排序 #include <iostream> #include<vector> #include<algorithm> using namespace std; const int N = 110; typedef pair<int, int> PII; vector<PII> alls; int cmp(PII item1, PII item2) { int size1 = item1.first * item1.second; int size2 = item2.first * item2.second; double x1= double(item1.first),y1=double(item1.second),x2=double(item2.first),y2=double(item2.second); double rate1 = min(x1/y1,y1/x1); double rate2 = min(x2/y2,y2/x2); int w1 = item1.first; int w2 = item2.first; if (size1 > size2) { return 1; } else if (size1 == size2) { if (rate1 < rate2) { return 1; } else if (rate1 == rate2) { if (w1 > w2) { return 1; } else if (w1 < w2) { return -1; } else { return 0; } } else { return -1; } } else { return -1; } } void swap(PII q[], int i, int j) { PII temp = q[i]; q[i] = q[j]; q[j] = temp; } void qsort(PII q[], int l, int r) { if (l >= r)return; int i = l - 1; int j = r + 1; int mid = (l+r)/2; PII x = q[mid]; while (i < j) { while (cmp(q[++i], x) == -1); while (cmp(q[--j], x) == 1); if (i < j) { swap(q, i, j); } } qsort(q, l, j); qsort(q, j + 1, r); } int main() { int n = 0; PII q[N]; scanf("%d", &n); for (int i = 0; i < n; i++) { int w, h = 0; scanf("%d%d", &w, &h); q[i] = {w, h}; } qsort(q, 0, n - 1); for (int i = 0; i < n; i++) { if(i==n-1){ printf("%d %d",q[i].first,q[i].second); }else{ printf("%d %d ", q[i].first, q[i].second); } } return 0; }
#include "bits/stdc++.h" using namespace std; //面积越小 //宽高比越大 ,宽比高: min(W/H,H/W) //宽越小 bool cmp(pair<double,double> a, pair<double,double> b){ double areaA = a.first * a.second; double areaB = b.first * b.second; if(areaA < areaB) return true; if(areaB < areaA) return false; double partionA_W_H = a.first < a.second ? a.first / a.second : a.second / a.first; double partionB_W_H = b.first < b.second ? b.first / b.second : b.second / b.first; if(partionA_W_H > partionB_W_H) return true; if(partionA_W_H < partionB_W_H) return false; return a.first <= b.first ? true : false; } int main(){ int N; cin >> N; vector<pair<double,double>> rects; //(W , H) rects.reserve(N); for(int i = 0; i < N && i < 100; ++i){ double W; double H; cin >> W >> H; rects.emplace_back(W,H); } sort(rects.begin(), rects.end(), cmp); for(int i = 0; i < N; ++i){ cout << rects[i].first << " " << rects[i].second << " "; } return 0; }
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApp2 { /// <summary> /// 给定N个矩形,每个矩形宽W米高H米 /// 请按以下规则将这N个矩形排序,输出排序后的矩形列表 /// /// 排序规则: /// 面积小的矩形排在面积大的矩形前面 /// 面积相同的矩形,按照宽高比排序,宽高比大的矩形排在宽高比小的矩形前面 /// 宽高比的定义为 min(W/H, H/W) /// 面积和宽高比都相同的矩形,按照宽排序,宽度更小的矩形排在宽度更大的矩形前面 /// </summary> public class JuXing { public int length { get; set; } public int width { get; set; } public int bili {get; set; } public int s { get; set; } public void Setbili() { int bili1 = this.length / this.width; int bili2 = this.width / this.length; if (bili1< bili2) { this.bili = bili1; }else { this.bili = bili2; } } public void SetS() { this.s= this.length* this.width; } } class Program { static void Main(string[] args) { int n = Convert.ToInt32(System.Console.ReadLine()); JuXing[] works = new JuXing[n]; string[] workValue = (System.Console.ReadLine()).Split(' '); for (int i = 0; i < n; i++) { works[i] = new JuXing() { width = Convert.ToInt32(workValue[2 * i]), length = Convert.ToInt32(workValue[2*(i+1)-1]) }; works[i].Setbili(); works[i].SetS(); //works[i].Setdeadline(Convert.ToInt32(workValue[0])); //works[i].Setcost(Convert.ToInt32(workValue[1])); //works[i].cost = Convert.ToInt32(workValue[1]); } ///按照面积比进行排序 //for (int i = 0; i < n - 1; i++) //{//控制比较轮次,一共 n-1 趟 // for (int j = 0; j < n - 1 - i; j++) // {//控制两个挨着的元素进行比较 // if (works[j].s > works[j + 1].s) // { // JuXing temp = works[j]; // works[j] = works[j + 1]; // works[j + 1] = temp; // } // //长宽比相同时按照面积排序 // if (works[j].s == works[j + 1].s) // { // if (works[j].bili < works[j + 1].bili) // { // JuXing temp = works[j]; // works[j] = works[j + 1]; // works[j + 1] = temp; // } // if (works[j].s== works[j + 1].s) // { // if (works[j].width > works[j + 1].width) // { // JuXing temp = works[j]; // works[j] = works[j + 1]; // works[j + 1] = temp; // } // } // } // } //} for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (works[j].s > works[j + 1].s) { JuXing temp = works[j]; works[j] = works[j + 1]; works[j + 1] = temp; } } } //面积相同时按照长宽比排序 for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (works[j].s == works[j + 1].s) { if (works[j].bili < works[j + 1].bili) { JuXing temp = works[j]; works[j] = works[j + 1]; works[j + 1] = temp; } } } } //面积相同时按照宽排序 for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (works[j].bili == works[j + 1].bili) { if (works[j].s ==works[j + 1].s) { if (works[j].width > works[j + 1].width) { JuXing temp = works[j]; works[j] = works[j + 1]; works[j + 1] = temp; } } } } } //打印结果 for (int i = 0; i < n; i++) { System.Console.Write(works[i].width); System.Console.Write(" "); System.Console.Write(works[i].length); if (i < n-1) { System.Console.Write(" "); } } System.Console.ReadLine(); } } }
#include<bits/stdc++.h> using namespace std; void helper(vector<vector<double>>&nums){ sort(nums.begin(),nums.end(),[&](auto&a,auto&b){ if(a[0]*a[1]==b[0]*b[1]){ if(min(a[0]/a[1],a[1]/a[0])==min(b[0]/b[1],b[1]/b[0])){ return a[0]<b[0]; } return min(a[0]/a[1],a[1]/a[0])>min(b[0]/b[1],b[1]/b[0]); }else{ return a[0]*a[1]<b[0]*b[1]; } }); } int main(){ int n;cin>>n; vector<vector<double>>Rec(n,vector<double>(2)); for(int i=0;i<2*n;i++){ if(i%2==1){ cin>>Rec[i/2][1]; }else{ cin>>Rec[i/2][0]; } } helper(Rec); for(int i=0;i<n;i++){ cout<<Rec[i][0]<<" "<<Rec[i][1]<<" "; } }
//照着流程来做的,中间用了冒泡排序,雷区在于getMin函数要转换为double,否则都是0无法比较 #include<iostream> #include<vector> #include<utility> using namespace std; int getV(pair<int, int>ret) { return ret.first * ret.second; } double getMinWH(pair<int, int>ret) { return min((double)ret.first / ret.second, (double)ret.second / ret.first); } void minRetengel(vector<pair<int, int>> &arr) { int len = arr.size(); for (int i = 0; i < len-1; i++) { for (int j = 0; j < len-1-i; j++) { if (getV(arr[j]) > getV(arr[j + 1])) { pair<int, int>temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } else if (getV(arr[j]) == getV(arr[j + 1])) { if (getMinWH(arr[j]) < getMinWH(arr[j + 1])) { pair<int, int>temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } else if (getMinWH(arr[j]) == getMinWH(arr[j + 1])) { if (arr[j] > arr[j + 1]) { pair<int, int>temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } } } int main(){ int N; cin>>N; int W,H; vector<pair<int,int>> ret; for(int i=0;i<N;i++){ while(cin>>W>>H) ret.push_back(make_pair(W,H)); } minRetengel(ret); for(auto i:ret){ cout<<i.first<<" "<<i.second<<" "; } }
采用新建对象、设置sort的cmp函数可以比较明晰地了解题目构成。
下文代码为py3.7环境
import sys from functools import cmp_to_key # 矩形对象暂存池 squarePool = [] # 创建一个矩形类 class Square(object): def __init__(self, w, h): self.w = w self.h = h self.size = w * h self.rate = min(float(w / h), float(h / w)) # 比较的CMP函数 def compare_square(squareA, squareB): # type: (Square,Square) -> int if squareA.size > squareB.size: return 1 elif squareA.size < squareB.size: return -1 else: if squareA.rate > squareB.rate: return -1 elif squareA.rate < squareB.rate: return 1 else: if squareA.w > squareB.w: return 1 elif squareA.w < squareB.w: return -1 else: return 0 def square_sort(): changeKey = cmp_to_key(lambda x, y: compare_square(x, y)) squarePool.sort(key=changeKey) def main(squareData): for i in range(0, len(squareData), 2): squarePool.append(Square(squareData[i], squareData[i + 1])) # ---调用分类--- square_sort() # ---输出--- for i in range(len(squarePool)): print("{} {} ".format(int(squarePool[i].w), int(squarePool[i].h)), end="") # 此处为输入行 countN = sys.stdin.readline() squareData = list(map(int, sys.stdin.readline().split())) main(squareData)
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); int N=sc.nextInt(); int[][] a=new int[N][2]; for (int i = 0; i < a.length; i++) { a[i][0]=sc.nextInt(); a[i][1]=sc.nextInt(); } Arrays.sort(a, new Comparator<int[]>() { public int compare(int[] a1,int[] a2) { if(a1[0]*a1[1]>a2[0]*a2[1]) {//比较之后大的返回1说明从小到大排序,返回-1说明从大到小排序 return 1; }else if(a1[0]*a1[1]==a2[0]*a2[1]) { double t1=Math.min((double)a1[0]/a1[1], (double)a1[1]/a1[0]); double t2=Math.min((double)a2[0]/a2[1], (double)a2[1]/a2[0]); if(t1<t2) { return 1; }else if(t1==t2) { if(a1[0]>a2[0]) { return 1; }else { return -1; } }else { return -1; } }else { return -1; } } }); for (int i = 0; i < a.length; i++) { if(i!=a.length-1) { System.out.print(a[i][0]+" "+a[i][1]+" "); }else { System.out.print(a[i][0]+" "+a[i][1]); } } } }
#include<stdio.h> #include<vector> #include<iostream> using namespace std; struct st { float rate; int s; int W; int H; }; int main(void) { int count = 0; cin>>count; vector<st> vt; while(count--) { st tmp; cin>>tmp.W; cin>>tmp.H; tmp.rate = min(tmp.H/(tmp.W*1.0f),tmp.W/(tmp.H*1.0f)); tmp.s = tmp.W*tmp.H; vt.push_back(tmp); } for(int i=0;i<=vt.size()-1;i++) { for(int j=i+1;j<=vt.size()-1;j++) if(vt[i].s>vt[j].s) swap(vt[i],vt[j]); else if(vt[i].s==vt[j].s) { if(vt[i].rate<vt[j].rate) swap(vt[i],vt[j]); else if(vt[i].rate==vt[j].rate) { if(vt[i].W>vt[j].W) swap(vt[i],vt[j]); } } } for(st sss:vt) { cout<<sss.W<<" "; cout<<sss.H<<" "; } }
用双向链表写的,不要在意我用Tree命名,只是链表 #include<stdio.h> #include<stdlib.h> typedef struct TreeNode{ float w; float h; float sq; float w_h; struct TreeNode* Left; struct TreeNode* Right; }*Tree; Tree CreatR(float W,float H,int S, float W_H,Tree P,Tree T){ P = malloc(sizeof(struct TreeNode)); P->h=H; P->w=W; P->sq=S; P->w_h=W_H; P->Left=T; P->Right=T->Right; T->Right=P; if(P->Right) P->Right->Left=P; return P; } Tree CreatL(float W,float H,int S, float W_H,Tree P,Tree T){ P = malloc(sizeof(struct TreeNode)); P->h=H; P->w=W; P->sq=S; P->w_h=W_H; P->Right=T; P->Left=T->Left; T->Left=P; if(P->Left) P->Left->Right=P; return P; } Tree Insert(float W,float H,int S, float W_H,Tree T){ Tree P=NULL; if(T==NULL) { T = malloc(sizeof(struct TreeNode)); T->h=H; T->w=W; T->sq=S; T->w_h=W_H; T->Left=T->Right=NULL; return T; } else if(S>T->sq) { P = CreatR( W,H,S,W_H,P,T); } else if(S==T->sq){ if(W_H<T->w_h){ P = CreatR( W,H,S,W_H,P,T); } else if(W_H==T->w_h){ if(W>=T->w){ P = CreatR( W,H,S,W_H,P,T); } else{ if(T->Left==NULL){ P = CreatL( W,H,S,W_H,P,T); } else P=Insert(W,H,S,W_H,T->Left); } } else{ if(T->Left==NULL){ P = CreatL( W,H,S,W_H,P,T); } else P=Insert(W,H,S,W_H,T->Left); } } else { if(T->Left==NULL){ P = CreatL( W,H,S,W_H,P,T); } else P=Insert(W,H,S,W_H,T->Left); } return P; } int main(void){ int N ; Tree T=NULL; float W,H; float S; float W_H; int min=0; scanf("%d",&N); for(int i=0;i<N;i++){ scanf("%f",&W); scanf("%f",&H); S=W*H; float b1=W/H; float b2=H/W; if(b1<=b2){ W_H=b1; } else{ W_H=b2; } T=Insert(W,H,S,W_H,T); while(T->Right) T=T->Right; // printf("%d %d ",(int)T->w,(int)T->h); } while(T->Left) T=T->Left; while(T) { printf("%d %d ",(int)T->w,(int)T->h); T=T->Right; } return 0; }
#include<iostream> #include<vector> #include<algorithm> using namespace std; class Solution { public: static bool cmp(pair<int, int>& A, pair<int, int>& B) { int SA = A.first * A.second; int SB = B.first * B.second; double AQA = min(double(A.first) / double(A.second), double(A.second) / double(A.first)); double BQB = min(double(B.first) / double(B.second), double(B.second) / double(B.first)); return SA == SB ? (AQA == BQB ? A.first < B.first : AQA > BQB) : SA < SB; } void Sort_rectangular(vector<pair<int,int>> &rectangulars) { sort(rectangulars.begin(), rectangulars.end(),cmp); } }; int main() { Solution solu; vector<pair<int, int>> rectangulars; int n, w, h; cin >> n; while (cin >> w >> h) { rectangulars.push_back({ w,h }); if (cin.get() == '\n') break; } solu.Sort_rectangular(rectangulars); for (auto rect : rectangulars) { cout << rect.first << " " << rect.second<<" "; } }
#include <iostream> #include <string> #include <sstream> #include <stdio.h> #include <queue> #include <vector> #define DEBUG_MY; struct M { int w,h; inline float Area() const { return (float)w * h; } inline float AspectRatio() const { //return (float)w / h; return std::min((float)h / w,(float)w / h); } inline friend bool operator<(const M& lhs, const M& rhs) { if(lhs.Area() > rhs.Area()) { return false; } else if (lhs.Area() < rhs.Area()) { return true; } else if (lhs.AspectRatio() < rhs.AspectRatio()) { return false; } else if (lhs.AspectRatio() > rhs.AspectRatio()) { return true; } else if (lhs.w > rhs.w) { return false; } else { return true; } } }; struct M_ComparatorGreater { bool operator()(const M& lhs, const M& rhs) noexcept { return !(lhs < rhs); } }; int main() { int N; std::cin >> N; std::priority_queue<M, std::vector<M>, M_ComparatorGreater> queue; for (int i = 0; i < N; ++i) { M m; std::cin >> m.w; std::cin >> m.h; queue.emplace(m); } while(!queue.empty()) { auto m = queue.top(); std::cout << m.w << " " << m.h << " "; queue.pop(); } return 0; }
#include<iostream> #include<vector> #include<algorithm> using namespace std; struct rectangle{ int w; int h; int getArea(){ return w*h; } double getScale(){ return min(w/double(h),h/double(w)); } }; bool cmp( rectangle a , rectangle b ){ if( a.getArea() != b.getArea() ) return a.getArea() < b.getArea(); else{ if( a.getScale() != b.getScale() )return a.getScale() > b.getScale(); else{ return a.w < b.w; } } } int main(){ int N; cin >> N; vector<rectangle> v(N); for( int i = 0 ; i < N ; i ++ ){ cin >> v[i].w >> v[i].h; } sort(v.begin(),v.end(),cmp); for( int i = 0 ; i < N ; i ++ ){ cout << v[i].w << " " << v[i].h << " "; } return 0; }
def minWH(width, height): return width/height if width/height < height/width else height/width n = int(input('')) rec = input('') reclist = rec.split(); width = []; height = []; for i in range(0, n): width.append(int(reclist[i*2])); height.append(int(reclist[i*2+1])); for i in range(0, n-1): for j in range(0, n-1-i): if (width[j] * height[j] > width[j+1] * height[j+1]): width[j], width[j+1] = width[j+1], width[j] height[j], height[j+1] = height[j+1], height[j] elif (width[j] * height[j] == width[j+1] * height[j+1]): if minWH(width[j], height[j]) < minWH(width[j+1], height[j+1]): width[j], width[j+1] = width[j+1], width[j] height[j], height[j+1] = height[j+1], height[j] #elif minWH(width[j], height[j]) == minWH(width[j+1], height[j+1]): else: if width[j] > height[j]: width[j], width[j+1] = width[j+1], width[j] height[j], height[j+1] = height[j+1], height[j] for i in range(0, n): print('%d %d ' % (width[i], height[i]), end = ' ')???为什么IDLE上运行没问题,这边就不能过