[贪心]Codeforces Equal Rectangles

You are given

You have to create

You want to all rectangles to have equal area. The area of the rectangle with sides

Your task is to say if it is possible to create exactly

You have to answer

Input

The first line of the input contains one integer

The first line of the query contains one integer

The second line of the query contains

Output

For each query print the answer to it. If it is impossible to create exactly

Example

input

Copy

5
1
1 1 10 10
2
10 5 2 10 1 1 2 5
2
10 5 1 10 5 1 1 1
2
1 1 1 1 1 1 1 1
1
10000 10000 10000 10000

output

Copy

YES
YES
NO
YES
YES

题意:

给你4*n个棍子，问能否用这些棍子组成n个面积相同的矩形

思路:

给n个棍子按大小排序，并统计其数量，第一次用最大和最小的棍子组成矩形，每次也是取出最大和最小的棍子组成矩形来判断是否和原矩形同面积，注意如果棍子用完了就要删掉这种棍子，如果棍子不够或多了就是不合法的要跳出循环

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int amn=1e4+5;
 4 int cnt[amn];
 5 set<int> s;
 6 set<int>::iterator it;
 7 set<int>::iterator rit;
 8 int main(){
 9     int q,n,in;
10     cin>>q;
11     while(q--){
12         memset(cnt,0,sizeof cnt);
13         cin>>n;
14         s.clear();
15         for(int i=1;i<=4*n;i++){
16             cin>>in;
17             s.insert(in);
18             cnt[in]++;
19         }
20         it=s.begin(),rit=s.end();rit--;
21         int a=*it,b=*rit;
22         int need=(a)*(b),num=0;
23         bool valid=1;
24         if(cnt[a]&&cnt[b]&&cnt[a]%2==0&&cnt[b]%2==0){
25                 cnt[a]-=2;cnt[b]-=2;
26                 num++;
27                 if(cnt[a]==0)
28                     s.erase(it++);
29                 else if(cnt[a]<0){
30                         valid=0;
31                         break;
32                 }
33                 if(a!=b&&cnt[b]==0)
34                     s.erase(rit--);
35                 else if(cnt[b]<0){
36                         valid=0;
37                         break;
38                 }
39             while(it!=s.end()&&s.size()){
40                 a=*it,b=*rit;
41                 int now=(a)*(b);
42                 if(now==need&&num<n){
43                     if(cnt[a]&&cnt[b]&&cnt[a]%2==0&&cnt[b]%2==0){
44                         cnt[a]-=2;cnt[b]-=2;
45                         num++;
46                         if(cnt[a]==0)
47                             s.erase(it++);
48                         else if(cnt[a]<0){
49                                 valid=0;
50                                 break;
51                         }
52                         if(a!=b&&cnt[b]==0)
53                             s.erase(rit--);
54                         else if(cnt[b]<0){
55                                 valid=0;
56                                 break;
57                         }
58                     }
59                     else{
60                         valid=0;
61                         break;
62                     }
63                 }
64                 else{
65                     valid=0;
66                     break;
67                 }
68             }
69         }
70         else{
71             valid=0;
72         }
73         if(valid&&num==n)cout<<"YES\n";
74         else cout<<"NO\n";
75     }
76 }
77 /***
78 给你4*n个棍子，问能否用这些棍子组成n个面积相同的矩形
79 给n个棍子按大小排序，并统计其数量，第一次用最大和最小的棍子组成矩形，每次也是取出最大和最小的棍子组成矩形来判断是否和原矩形同面积，注意如果棍子用完了就要删掉这种棍子，如果棍子不够或多了就是不合法的要跳出循环
80 ***/