虽然分类在数据结构里,但是实际上是个贪心题......
我自己一开始想到了一个错误的贪心。后来发现对于相等值的处理不行。
有个很神的转化,就是把排好序的队列以及对应的原下标都给搞出来。
然后考虑其中一段:若这一段属于同一个双端队列,那么原下标一定呈单谷状。
相等的值如何处理呢?因为相等的值可以任意在排序后的序列里交换位置,所以我们可以任意设计它们的原下标而达到单谷状态来为我们所用。
所以特判一下就好了。时间O(nlogn),因为有排序。
(惨痛的教训:把 == 写成了 = )
1 /************************************************************** 2 Problem: 2457 3 Language: C++ 4 Result: Accepted 5 Time:452 ms 6 Memory:3948 kb 7 ****************************************************************/ 8 9 #include <cstdio> 10 #include <algorithm> 11 const int N = 200010; 12 13 struct Number { 14 int val, num, num_up; 15 bool del; 16 bool operator < (const Number &x) const { 17 if(val != x.val) { 18 return val < x.val; 19 } 20 return num < x.num; 21 } 22 }num[N]; 23 24 int main() { 25 //freopen("in.in", "r", stdin); 26 //freopen("my.out", "w", stdout); 27 int n; 28 scanf("%d", &n); 29 for(int i = 1; i <= n; i++) { 30 scanf("%d", &num[i].val); 31 num[i].num = num[i].num_up = i; 32 } 33 std::sort(num + 1, num + n + 1); 34 35 int t = 1; 36 for(int i = 2; i <= n; i++) { /// 去重 37 if(num[i].val == num[t].val) { 38 num[t].num_up = num[i].num; 39 num[i].del = 1; 40 } 41 else { 42 t = i; 43 } 44 } 45 46 47 int now = num[1].num; 48 int k = 2;/// 1 up 2 down 49 int ans = 1; 50 51 for(int i = 2; i <= n; i++) { 52 if(num[i].del) { 53 continue; 54 } 55 if(num[i].num == num[i].num_up) { 56 bool f = num[i].num < now; 57 if(k == 1) { /// up 58 if(f) { 59 ans++; 60 k = 2; 61 } 62 } 63 else { /// k == 2 down 64 if(!f) { 65 k = 1; 66 } 67 } 68 now = num[i].num; 69 } 70 else { /// 多个 71 if(k == 1) { /// up 72 if(num[i].num > now) { 73 now = num[i].num_up; 74 } 75 else if(num[i].num_up < now) { 76 ans++; 77 k = 2; 78 now = num[i].num; 79 } 80 else { /// 中间 81 ans++; 82 k = 2; 83 now = num[i].num; 84 } 85 } 86 else { /// down 87 if(num[i].num > now) { 88 k = 1; 89 now = num[i].num_up; 90 } 91 else if(num[i].num_up < now) { 92 now = num[i].num; 93 } 94 else { /// 中间 95 k = 1; 96 now = num[i].num_up; 97 } 98 } 99 } 100 //printf("%d %d %d %d\n", num[i].val, ans, k, now); 101 } 102 printf("%d", ans); 103 return 0; 104 }
© 著作权归作者所有
举报
发表评论
0/200