贪心

Wikioi 1128 导弹拦截

题目描述 Description

经过11 年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为0 时，则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径。而当天的使用代价，就是所有系统工作半径的平方和。
某天，雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段，所以只有两套系统投入工作。如果现在的要求是拦截所有的导弹，请计算这一天的最小使用代价。

数据范围
对于10%的数据，N = 1
对于20%的数据，1 ≤ N ≤ 2
对于40%的数据，1 ≤ N ≤ 100
对于70%的数据，1 ≤ N ≤ 1000
对于100%的数据，1 ≤ N ≤ 100000，且所有坐标分量的绝对值都不超过1000。

输入描述 Input Description

第一行包含4 个整数x1、y1、x2、y2，每两个整数之间用一个空格隔开，表示这两套导弹拦截系统的坐标分别为(x1, y1)、(x2, y2)。
第二行包含1 个整数N，表示有N 颗导弹。接下来N 行，每行两个整数x、y，中间用一个空格隔开，表示一颗导弹的坐标(x, y)。不同导弹的坐标可能相同。

输出描述 Output Description

输出只有一行，包含一个整数，即当天的最小使用代价。

样例输入 Sample Input

0 0 10 0
2
-3 3
10 0

样例输出 Sample Output

数据范围及提示 Data Size & Hint

两个点(x1, y1)、(x2, y2)之间距离的平方是(x1− x2)^2+(y1−y2)^2。
两套系统工作半径r1、r2 的平方和，是指r1、r2 分别取平方后再求和，即r1^2+r2^2。

思路：

贪心，把所有导弹到两个拦截装置的距离求出来，然后按照与第一个装置的距离为关键字进行排序，然后从大到小算出两个装置的设置半径，最后输出结果

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 
 6 using namespace std;
 7 const int maxn = 10000000;
 8 int n,xa,xb,ya,yb,total = maxn;
 9 int x[maxn],y[maxn];
10 
11 struct bomb{
12     int s1,s2,num;
13 };
14 bomb a[maxn];
15 
16 bool cmp(bomb n1,bomb n2){
17     if(n1.s1 < n2.s1) return true;
18     else return false;
19 }
20 int main(){    
21     cin>>xa>>ya>>xb>>yb>>n;
22 
23     
24     int r1 = 0,r2 = 0,temp = 0,total = maxn;
25     for(r1 = 0;r1 < n;r1++){
26        cin>>x[r1]>>y[r1];
27        a[r1].s1 = (x[r1] - xa) * (x[r1] - xa) + (y[r1] - ya) * (y[r1] - ya);
28        a[r1].s2 = (x[r1] - xb) * (x[r1] - xb) + (y[r1] - yb) * (y[r1] - yb);
29        a[r1].num = r1;
30        
31 }
32 
33     sort(a,a+n,cmp);
34     r1 = n -1;
35     r2 = 0;
36 
37     for(r1 = n - 1;r1 >= 0;r1--){
38         r2 = r1 + 1;
39         if(a[r2].s2 > temp && r2 < n) temp = a[r2].s2;
40             
41 
42         if(total > temp + a[r1].s1) total = temp + a[r1].s1;
43     }
44         if(a[0].s2 > temp) temp = a[0].s2;    
45         if(total > temp) total = temp;
46 
47     
48     cout<<total;
49     return 0;
50 }

View Code

Wikioi 1001 舒适的线路

题目描述 Description

Z小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。
Z小镇附近共有
N(1<N≤500)个景点（编号为1,2,3,…,N），这些景点被M（0<M≤5000）条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。也许是为了保护该地的旅游资源，Z小镇有个奇怪的规定，就是对于一条给定的公路Ri，任何在该公路上行驶的车辆速度必须为Vi。频繁的改变速度使得游客们很不舒服，因此大家从一个景点前往另一个景点的时候，都希望选择行使过程中最大速度和最小速度的比尽可能小的路线，也就是所谓最舒适的路线。

输入描述 Input Description

第一行包含两个正整数，N和M。
接下来的M行每行包含三个正整数：x，y和v（1≤x,y≤N，0 最后一行包含两个正整数s，t，表示想知道从景点s到景点t最大最小速度比最小的路径。s和t不可能相同。

输出描述 Output Description

如果景点s到景点t没有路径，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。

样例输入 Sample Input

样例1
4 2
1 2 1
3 4 2
1 4

样例2
3 3
1 2 10
1 2 5
2 3 8
1 3

样例3
3 2
1 2 2
2 3 4
1 3

样例输出 Sample Output

样例1
IMPOSSIBLE

样例2
5/4

样例3
2

数据范围及提示 Data Size & Hint

N(1<N≤500)

M（0<M≤5000）

Vi在int范围内

思路：

把边从大到小排序，然后枚举最大边，再不断添加最小边，直到生成树里边包含原点和终点，然后比较答案

代码：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<string>
  5 #include<algorithm>
  6 
  7 using namespace std;
  8 struct Edge{
  9     int x;
 10     int y;
 11     int v;
 12 };
 13 const int maxn = 100000;
 14 int n,m,s,t,pre[maxn];
 15 Edge edge[maxn];
 16 void init(){
 17     cin>>n>>m;
 18     for(int i = 0; i < m;i++){
 19         cin>>edge[i].x>>edge[i].y>>edge[i].v;
 20         
 21     }
 22     cin>>s>>t;
 23     for(int i = 1;i <= n;i++) pre[i] = i;
 24 }
 25 bool cmp(Edge a,Edge b){
 26     return a.v > b.v;
 27 }
 28 int gcd(int a,int b)
 29 {
 30     if (a < b)
 31         swap(a, b);
 32     return b == 0 ? a : gcd(b, a % b);
 33 }
 34 int find(int x)                                                                                              
 35 { 
 36     int r=x;
 37     while ( pre[r ] != r )                                                                                     
 38           r=pre[r ];
 39  
 40     int i=x , j ;
 41     while( i != r )                                                                                                      
 42     {
 43          j = pre[ i ];
 44          pre[ i ]= r ;
 45          i=j;
 46     }
 47     return r ;
 48 }
 49  
 50  
 51 void join(int x,int y)                                                                                                  
 52                                                                                              
 53 {
 54     int fx=find(x),fy=find(y);
 55     if(fx!=fy)
 56         pre[fx ]=fy;
 57 }
 58 
 59 void print(int so,int mo){
 60     
 61     if(so == -1 && mo == -1) cout<<"IMPOSSIBLE"<<endl;
 62     else {
 63         int g = gcd(so,mo);
 64         if(mo/g != 1)cout<<so/g<<"/"<<mo/g<<endl;
 65         else cout<<so/g<<endl;
 66     }
 67 
 68 }
 69 void work(){
 70     double ans_max,ans_min,fx,fy;
 71     double rate = 100000000;
 72     int son = -1,mother = -1;
 73     sort(edge,edge+m,cmp);
 74     for(int i = 0;i < m;i++){
 75         for(int o = 1;o <= n;o++) pre[o] = o;
 76         rate = 100000000;
 77         ans_max = edge[i].v;
 78         ans_min = edge[i].v;
 79         fx = -1;
 80         fy = -1;
 81         for(int j = i;j < m;j++){
 82             join(edge[j].x,edge[j].y);
 83             ans_min = edge[j].v;
 84             int fx=find(s),fy=find(t);
 85             if(fx != fy){
 86                 ans_min = edge[j].v;
 87             }else{
 88                 if(ans_max / ans_min < rate){
 89                     rate = ans_max / ans_min;
 90                      son = ans_max;
 91                      mother = ans_min;
 92                 }
 93                 continue;
 94             }
 95         }
 96     }
 97     print(son,mother);
 98         
 99     
100 }
101 
102 int main(){
103     init();
104     work();
105     return 0;
106 }

View Code

Wikioi 1198 国王游戏

题目描述 Description

恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

输入描述 Input Description

第一行包含一个整数 n，表示大臣的人数。

第二行包含两个整数a和b，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来n行，每行包含两个整数a和b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

输出描述 Output Description

输出只有一行，包含一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的

金币数。

样例输入 Sample Input

1 1

2 3

7 4

4 6

样例输出 Sample Output

数据范围及提示 Data Size & Hint

【输入输出样例说明】

按 1、2、3号大臣这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；

按 1、3、2这样排列队伍，获得奖赏最多的大臣所获得金币数为2；

按 2、1、3这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；

按 2、3、1这样排列队伍，获得奖赏最多的大臣所获得金币数为 9；

按 3、1、2这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；

按 3、2、1这样排列队伍，获得奖赏最多的大臣所获得金币数为 9。

因此，奖赏最多的大臣最少获得 2 个金币，答案输出 2。

【数据范围】

对于20%的数据，有1≤ n≤ 10，0 < a、b < 8；

对于40%的数据，有1≤ n≤20，0 < a、b < 8；

对于60%的数据，有1≤ n≤100；

对于60%的数据，保证答案不超过 10^9；

对于100%的数据，有 1 ≤ n ≤1,000，0 < a、b < 10000。

思路:
（摘自夏令营课件）

首先，相邻两个人交换位置，对其他人获得的奖赏没有影响。设A、B相邻，A的左右手分别是a、b， B的左右手分别是c、d。A、B之前大臣左手的乘积是t。 A在B前，A获得t/b，B获得at/d。 B在A前，A获得ct/b，B获得t/d。因为t/b＜ct/b，t/d＜at/d 所以总的最大值是at/d或ct/b

a/d＞c/b，即ab＞cd时， A在B前会更大，所以让B在A前 a/d＜c/b，即ab＜cd时， B在A前会更大，所以让A在B前所以按左右手上数的乘积从小到大排序。

代码：

（注意高精度）

  1 #include <cstdio> 
  2 #include<algorithm> 
  3 #include <cmath> 
  4 #include <iostream> 
  5 #include <cstring> 
  6  
  7 using namespace std; 
  8  
  9 const int P=10000,L=5000,W=4; 
 10 char s[L*W]; 
 11 struct Big 
 12   { 
 13     int len;int data[L];bool fu; 
 14     void clear()  
 15       { 
 16         memset(data,0,sizeof(data)); 
 17         len=0;fu=false; 
 18       } 
 19     int& operator [] (int k) 
 20       { 
 21         return data[k]; 
 22       } 
 23     void operator = (int k) 
 24       { 
 25         clear(); 
 26         if (k<0) fu=true,k=-k;else fu=false; 
 27         len=0; 
 28         while (k) data[++len]=k%P,k/=P;  
 29         if (len==0) len=1; 
 30       } 
 31     bool operator < (Big b) 
 32       { 
 33         bool t=false; 
 34         if (fu && !b.fu) return true; 
 35         if (!fu && b.fu) return false; 
 36         if (fu && b.fu) t=true; 
 37         if (len<b.len) return true^t; 
 38         if (len>b.len) return false^t; 
 39         for (int i=len;i;--i) 
 40           { 
 41             if (data[i]<b[i]) return true^t; 
 42             if (data[i]>b[i]) return false^t; 
 43           } 
 44         return false; 
 45       } 
 46     bool operator <= (Big b) 
 47       { 
 48         bool t=false; 
 49         if (fu && !b.fu) return true; 
 50         if (!fu && b.fu) return false; 
 51         if (fu && b.fu) t=true; 
 52         if (len<b.len) return true^t; 
 53         if (len>b.len) return false^t; 
 54         for (int i=len;i;--i) 
 55           { 
 56             if (data[i]<b[i]) return true^t; 
 57             if (data[i]>b[i]) return false^t; 
 58           } 
 59         return true; 
 60       } 
 61     bool operator > (Big b) 
 62       { 
 63         bool t=false; 
 64         if (fu && !b.fu) return false; 
 65         if (!fu && b.fu) return true; 
 66         if (fu && b.fu) t=true; 
 67         if (len<b.len) return false^t; 
 68         if (len>b.len) return true^t; 
 69         for (int i=len;i;--i) 
 70           { 
 71             if (data[i]<b[i]) return false^t; 
 72             if (data[i]>b[i]) return true^t; 
 73           } 
 74         return false; 
 75       } 
 76     bool operator >= (Big b) 
 77       { 
 78         bool t=false; 
 79         if (fu && !b.fu) return false; 
 80         if (!fu && b.fu) return true; 
 81         if (fu && b.fu) t=true; 
 82         if (len<b.len) return false^t; 
 83         if (len>b.len) return true^t; 
 84         for (int i=len;i;--i) 
 85           { 
 86             if (data[i]<b[i]) return false^t; 
 87             if (data[i]>b[i]) return true^t; 
 88           } 
 89         return true; 
 90       } 
 91     bool operator == (Big b) 
 92       { 
 93         if (fu!=b.fu) return false; 
 94         if (len<b.len) return false; 
 95         if (len>b.len) return false; 
 96         for (int i=len;i;--i) 
 97           if (data[i]!=b[i]) return false; 
 98         return true; 
 99       } 
100     bool operator == (int k) 
101       { 
102         if (k<0) 
103           { 
104             if (!fu) return false; 
105             k=-k; 
106           } else if (fu) return false; 
107         if (k>=P) 
108           { 
109             Big b;b=k; 
110             return *this==b; 
111           } 
112             else return len==1 && data[1]==k; 
113       } 
114     bool operator != (Big b) 
115       { 
116         if (fu!=b.fu) return true; 
117         if (len<b.len) return true; 
118         if (len>b.len) return true; 
119         for (int i=len;i;--i) 
120           if (data[i]!=b[i]) return true; 
121         return false; 
122       } 
123     bool operator != (int k) 
124       { 
125         if (k<0) 
126           { 
127             if (!fu) return true; 
128             k=-k; 
129           } else if (fu) return true; 
130         if (k>=P) 
131           { 
132             Big b;b=k; 
133             return *this!=b; 
134           } 
135             else return !(len==1 && data[1]==k); 
136       } 
137     Big operator + (Big b) 
138       { 
139         Big a=*this,c;c.clear(); 
140         if (a.fu && b.fu)  
141           { 
142             a.fu=false;b.fu=false;c=a+b; 
143             if (c.len!=1 || c[1]!=0) c.fu=true; 
144             return c; 
145           } 
146         if (a.fu && !b.fu)  
147           {a.fu=false;return b-a;} 
148         if (!a.fu && b.fu) 
149           {b.fu=false;return a-b;}  
150         a.len=max(a.len,b.len); 
151         for (int i=1;i<=a.len;++i) 
152           { 
153             a[i+1]+=(a[i]+b[i])/P; 
154             a[i]=(a[i]+b[i])%P; 
155           } 
156         if (a[a.len+1]) ++a.len; 
157         while (a[a.len]==0 && a.len>1) --a.len; 
158         return a; 
159       } 
160     Big operator + (int k) 
161       { 
162         Big a=*this,b;b=k; 
163         return a+b; 
164       } 
165     Big operator - (Big b) 
166       { 
167         Big a=*this,c;c.clear(); 
168         if (a.fu && !b.fu) 
169           { 
170             a.fu=false;b.fu=false;c=a+b; 
171             if (c.len!=1 || c[1]!=0) c.fu=true; 
172             return c; 
173           } 
174         if (a.fu && b.fu)  
175           { 
176             a.fu=false;b.fu=false;return b-a; 
177           } 
178         if (!a.fu && b.fu) 
179           { 
180             b.fu=false; return a+b; 
181           } 
182         if (a<b) swap(a,b),a.fu=true;else a.fu=false; 
183         for (int i=1;i<=a.len;++i) 
184           { 
185             if (a[i]<b[i]) a[i]+=P,--a[i+1]; 
186             a[i]-=b[i]; 
187           } 
188         while (a[a.len]==0 && a.len>1) --a.len; 
189         if (a.len==1 && a[1]==0) a.fu=false; 
190         return a; 
191       } 
192     Big operator - (int k) 
193       { 
194         Big a=*this,b;b=k; 
195         return a-b; 
196       } 
197     Big operator * (Big b) 
198       { 
199         Big c;c.clear(); 
200         c.len=len+b.len-1; 
201         for (int i=1;i<=len;++i) 
202           for (int j=1;j<=b.len;++j) 
203             { 
204               c[i+j-1]+=data[i]*b[j]; 
205               c[i+j]+=c[i+j-1]/P; 
206               c[i+j-1]%=P; 
207             } 
208         if (c[c.len+1]) ++c.len; 
209         while (c[c.len]==0 && c.len>1) --c.len; 
210         c.fu=fu^b.fu; 
211         if (c.len==1 && c[1]==0) c.fu=false; 
212         return c; 
213       } 
214     Big operator * (int k) 
215       { 
216         Big a=*this; 
217         if (k<0) a.fu=!a.fu,k=-k; 
218         if (k>=P)  
219           { 
220             Big b;b=k; 
221             return a*b; 
222           } 
223         for (int i=1;i<=a.len;++i) a[i]*=k; 
224         for (int i=1;i<=a.len;++i) 
225           a[i+1]+=a[i]/P,a[i]%=P; 
226         while (a[a.len+1])  
227           { 
228             ++a.len; 
229             a[a.len+1]=a[a.len]/P; 
230             a[a.len]%=P; 
231           } 
232         while (a[a.len]==0 && a.len>1) --a.len; 
233         if (a.len==1 && a[1]==0) a.fu=false; 
234         return a; 
235       } 
236     Big operator / (int k) 
237       { 
238         Big a=*this;int g=0; 
239         if (k<0) a.fu=!a.fu,k=-k; 
240         for (int i=a.len;i;--i) 
241           { 
242             a[i]+=g*P; 
243             g=a[i]%k; 
244             a[i]/=k; 
245           } 
246         while (a[a.len]==0 && a.len>1) --a.len; 
247         if (a.len==1 && a[1]==0) a.fu=false; 
248         return a; 
249       } 
250     Big operator % (int k) 
251       { 
252         Big b;b=k; 
253         return *this%b; 
254       } 
255     Big operator / (Big b) 
256       { 
257         Big c,d;c=0;d=0;c.fu=fu^b.fu;b.fu=false; 
258         for (int i=len;i;--i) 
259           { 
260             d=d*P+data[i]; 
261             int ans=0,l=0,r=P-1; 
262             while (l<=r) 
263               { 
264                 int mid=(l+r)>>1; 
265                 if (b*mid<=d) ans=mid,l=mid+1; 
266                 else r=mid-1; 
267               } 
268             c[i]=ans; 
269             d=d-b*c[i]; 
270           } 
271         c.len=len; 
272         while (c[c.len]==0 && c.len>1) --c.len; 
273         return c; 
274       } 
275     Big operator % (Big b) 
276       { 
277         Big c,d;c=0;d=0;c.fu=fu^b.fu;b.fu=false; 
278         for (int i=len;i;--i) 
279           { 
280             d=d*P+data[i]; 
281             int ans=0,l=0,r=P-1; 
282             while (l<=r) 
283               { 
284                 int mid=(l+r)>>1; 
285                 if (b*mid<=d) ans=mid,l=mid+1; 
286                 else r=mid-1; 
287               } 
288             c[i]=ans; 
289             d=d-b*c[i]; 
290           } 
291         c.len=len; 
292         while (c[c.len]==0 && c.len>1) --c.len; 
293         d=*this-b*c; 
294         return d; 
295       } 
296     Big operator ^ (int t) 
297       { 
298         Big a=*this,ans;ans=1; 
299         while (t) 
300           { 
301             if (t&1) ans=ans*a;t>>=1;a=a*a; 
302           } 
303         return ans; 
304       }     
305     void read() 
306       { 
307         scanf("%s",s); 
308         clear(); 
309         len=1; 
310         int pow=1,t=1,l=strlen(s),stop=0; 
311         if (s[0]=='-') fu=true,stop=1; 
312         for (int i=l-1;i>=stop;--i) 
313           { 
314             if (t>W) t=pow=1,++len; 
315             data[len]+=pow*(s[i]-'0'); 
316             ++t,pow*=10; 
317           } 
318       } 
319     void write() 
320       { 
321         if (fu) printf("%c",'-'); 
322         printf("%d",data[len]); 
323         for (int i=len-1;i;--i) 
324           { 
325             if (data[i]<10) putchar('0'); 
326             if (data[i]<100) putchar('0'); 
327             if (data[i]<1000) putchar('0'); 
328             printf("%d",data[i]); 
329           } 
330       } 
331     void writeln() 
332       { 
333         write();printf("
"); 
334       } 
335   } ;
336   struct Man{
337       int l;
338       int r;
339       Big sum;
340   };
341   bool cmp(Man a,Man b){
342       return (a.l * a.r) < (b.l * b.r);
343   }
344   Big ans,lft; 
345   Man man[1005];
346 int main(){
347     int n,fl,fr;
348     cin>>n;
349     cin>>fl>>fr;
350     for(int i = 0;i < n;i++){
351         cin>>man[i].l>>man[i].r;
352         man[i].sum = man[i].l * man[i].r;
353     }
354     sort(man,man + n,cmp);
355     ans = 0;
356     lft = fl;
357     for(int i = 0;i < n;i++){
358         if(lft * man[i].r > ans) ans = lft / man[i].r;
359         lft = lft * man[i].l;
360     }
361     if(ans == 0) cout<<1<<endl;
362     else ans.writeln();
363 
364     return 0;
365 }

View Code

田忌赛马，某个普及组题