首页 > 代码库 > 2017暑假 贪心

2017暑假 贪心

2024-10-29 15:28:38   207人阅读

  • uva 10382 - Watering Grass

题目地址： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1323

洒水器洒水区域是圆形，草地是矩形，勾股定理求出洒水器所撒横向范围然后贪心就好了。

ps:如果洒水器洒水直径 r*2 小于草地宽度 w ，这个装置就非常很超级没用，这种数据就不需要处理了，否则会tle...

代码如下：

技术分享 
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef pair< double,double > pi;
 5 
 6 int main()
 7 {
 8     int n, l, w;
 9 
10     while(~scanf("%d%d%d", &n, &l, &w))
11     {
12         priority_queue < pi, vector<pi>, greater<pi> > q;
13         for(int i = 0; i < n; i++)
14         {
15             double p;
16             int r;
17             scanf("%lf%d", &p, &r);
18             if(r*2 < w) continue;//
19             double temp = sqrt((double)r*r - (double)w*w/4.0);
20             pi cur;
21             cur.first = p - temp, cur.second = p + temp;
22             q.push(cur);
23         }
24 
25         double le = 0.0, ri = 0.0;
26         int sum = 0, flag = 0;
27         while(!q.empty())
28         {
29             pi temp = q.top();
30             if(temp.first > ri) break;
31             else
32             {
33                 while(!q.empty() && q.top().first <= le)
34                 {
35                     pi cur = q.top();q.pop();
36                     if(cur.second > ri) ri = cur.second;
37                 }
38                 le = ri;
39                 sum++;
40                 if(ri >= l)
41                 {
42                     flag = 1;
43                     break;
44                 }
45             }
46         }
47 
48         if(flag) printf("%d\n", sum);
49         else    puts("-1");
50     }
51     return 0;
52 }
View Code

 

  • uva 10905 - Children‘s Game

题目地址： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1846

每个字符的“大小”和数字的大小是一样的，string数组收进来排个序输出就好了。。。

排序方法：数字首位大的在前，首位大小相同的比如 9、90 ，直接比较 990 和 909的大小即可。

代码如下：

技术分享 
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 bool cmp(string x, string y)
 5 {
 6     if(x[0] == y[0])
 7     {
 8         string a = x + y, b = y + x;
 9         return a > b;
10     }
11     return x > y;
12 }
13 
14 int main()
15 {
16     int n;
17     while(~scanf("%d", &n) && n)
18     {
19         string s[55];
20         for(int i = 0; i < n; i++)  cin >> s[i];
21         sort(s, s+n, cmp);
22         for(int i = 0; i < n; i++) cout << s[i];
23         printf("\n");
24     }
25     return 0;
26 }
View Code

 

  • uva 11134 - Fabled Rooks

题目地址：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2075

就是一排一排地摆吧。。。补完剧再回来做。

2017暑假 贪心


联系
我们