Why so serious? --[NKU]schindlerlee

2010年03月28日星期日.codeforces beta6

2010年03月28日星期日.codeforces beta6

A:三角形两边之和大于第三边
B:暴力搜一下
C:模拟

 1 
 2 scanf("%d\n",&n);
 3 for (i = 0;i < n;i++) {
 4   scanf("%d",a + i);
 5 }
 6 int L = 0,R = n - 1,time1 = 0,time2 = 0,ans1 = 0,ans2 = 0;
 7 while (L <= R) {
 8   if (time1 < time2) {
 9       time1 += a[L++] ,ans1 ++;
10   }else if (time1 > time2) {
11       time2 += a[R--] ,ans2 ++;
12   }else {
13       time1 += a[L++] ,ans1 ++;
14   }
15 }
16 printf("%d %d\n",ans1,ans2);

D:题目改了,和比赛的时候不一样了,数据范围很小,dfs
E:RMQ + binary_search
给出n个数和一个范围K。
找出最长的连续的数,其中最大值和最小值的差不超过K
一个直觉的想法是
for(i = 0;i < n;i++) {
    int L = a[i],R = a[i];
    for (j = i + 1;j < n && R - L <= K;j++) {
        更新L,R
    }
    更新answer
}

但是n是10^5,n^2会超时。
求区间最大值最小值可以用rmq,O(nlogn)预处理,O(1)的得到。
一定存在一个j,使得a [i ... j]合法,a[j + 1 ..n]不合法。
好的方法是二分搜索到这个j,水点的方法可以从后往前找j。

RMQ 可以线段树,也可以SparseTable
总复杂度O(nlogn)
codeforces 可以看代码,想看的会去找吧。这里的二分搜有trick,求的是upper_bound不是一般写的lower_bound,需要调整。

posted on 2010-03-28 01:17 schindlerlee 阅读(1263) 评论(3)  编辑 收藏 引用 所属分类: 解题报告

Feedback

# re: 2010年03月28日星期日.codeforces beta6 2010-03-28 07:54 MasterLuo

我觉得E二分是会有问题的?并不满足单调性。
我有个想法就是用二条扫描线,外加一个最小堆来维护。  回复  更多评论   

# re: 2010年03月28日星期日.codeforces beta6 2010-03-28 10:08 schindlerlee

@MasterLuo
我觉得是单调的,肯定是前边合法,后边不合法了
还有就是我相信sgu那帮人做的动不动上百组的测试数据...
另外,我不太明白你说的扫描,我感觉那样岂不是n^2了?


 1 for (i = 0;i < n;i++) {
 2     int L = i,R = n;
 3     while (L < R) {
 4         int mid = (L + R) / 2;
 5         int tmp = bigrmq(i,mid) - smlrmq(i,mid);
 6         if (tmp <= diff) {
 7             if (L == mid) { break;}
 8             L = mid;
 9         }else {
10             if (R == mid + 1) {break;}
11             R = mid + 1;
12         }
13     }
14     int tmp = L - i + 1;
15     if (tmp > ans) {
16         ans = tmp;
17         记录结果
18     }else if (tmp == ans) {
19         记录结果
20     }
21 }


  回复  更多评论   

# re: 2010年03月28日星期日.codeforces beta6 2010-03-28 10:48 MasterLuo

@schindlerlee
扫描是NlogN的,因为我们从第一个开始每加入一个数后如果引起了不满足题意条件,那么一定是最新加入的那个数引起的,现在还在堆中的最大数与最小数之间一定会有一个要退出,可以证明它与后面要加入的数也不能满足条件。于是我们找到位置在前面的那个数,把它前面所有的数都删除。再判断,直到满足条件为止。这样每个数就只进优先队列一次,也只出优先队列一次。 我写了下代码,验证了一下,过上去过了。
C++语言: 临时自用代码


int n, k, maxVal, minVal;
int arr[100000], ans = 0, maxLen = 1, red[100000][2];
struct Node {
int loc, val;
}node;
struct CMP_1 {
bool operator()(const Node& min, const Node& max) {
if((min.val > max.val) ||(min.val == max.val && min.loc > max.loc))
return true;
return false;
}
};
struct CMP_2 {
bool operator()(const Node& min, const Node& max) {
if((min.val < max.val) || (min.val == max.val && min.loc > max.loc))
return true;
return false;
}
};
int last = 0;
int main() {
scanf("%d %d", &n, &k);
for(int i = 0; i < n; ++i) {
scanf("%d", &arr[i]);
}
priority_queue<Node, vector<Node>, CMP_1> pri;
priority_queue<Node, vector<Node>, CMP_2> pri2;

for(int i = 0; i < n; ++i) {
node.val = arr[i];
node.loc = i;
pri.push(node);
pri2.push(node);

int minVal = pri.top().val;
int maxVal = pri2.top().val;

while(maxVal - minVal > k) {
int lt = min(pri.top().loc, pri2.top().loc);
while(!pri.empty() && pri.top().loc <= lt) {
pri.pop();
}
while(!pri2.empty() && pri2.top().loc <= lt) {
pri2.pop();
}
last = lt + 1;
minVal = pri.top().val;
maxVal = pri2.top().val;
}
int tmpLen = i - last + 1;
if(tmpLen == maxLen) {
red[ans][0] = last;
red[ans][1] = i;
++ans;
}
if(tmpLen > maxLen) {
red[0][0] = last;
red[0][1] = i;
ans = 1;
maxLen = tmpLen;
}
}
printf("%d %d\n", maxLen, ans);
for(int i = 0; i < ans; ++i) {
printf("%d %d\n", red[i][0] + 1, red[i][1] + 1);
}
return 0;
}

  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理