C1-C-小田田浇花

题目描述

题面 有n朵花，编号0∼n−1，一开始都是干旱状态。

每次操作会都使[L,R]区间内的花朵状态发生改变，也就是说，对于花i，L≤i≤R，如果i是干旱状态，则小田田会浇水让花变成正常状态，而如果i是正常状态，会由于天气原因变为干旱状态。

请问k次操作后有多少花是正常状态。

输入 多组输入数据

每组数据第一行两个数n,k（1≤n≤109,1≤k≤105）

接下来k行，每行两个数l,r（0≤l≤r≤n−1）

输出 每组数据一行一个数，表示最后正常状态的花的个数

输入样例

10 1 2 6

输出样例

5

Hint 排序+思维

思路分析

被浇过奇数次的花为正常状态，被浇过偶数次的花为干旱状态。 如果两个区间重叠，形成三个小区间，第一个第三个为奇数区间正常状态，第二个区间为偶数区间干旱状态。 三个及多个区间同理。 算法为：把给出的区间左右端点放在一起排序，然后从左至右遍历，最后的

AC代码

#include<stdio.h> int a[200010]; int cmp(const void *L,const void *R); int main() { int i,n,k; while(scanf("%d%d",&n,&k)!=EOF) { for(i=0;i<2*k;i+=2) { scanf("%d%d",&a[i],&a[i+1]); a[i+1]++; } qsort(a,2*k,sizeof(a[0]),cmp); int ans=0; int cnt=0; for(i=0;i<2*k-1;i++) { cnt++; if(cnt%2==1) { ans+=(a[i+1]-a[i]); } } printf("%d\n",ans); } return 0; } int cmp(const void *L,const void *R) { return *(int*)L-*(int*)R; }

总结

1.编程问题的数学抽象和建模 2.C语言库函数快排，要先自己写一个比较函数cmp

//升序函数 int cmp(const void *a,const void *b) { return *(int*)a-*(int*)b; } //降序函数 int cmp(const void *a,const void *b) { return *(int*)b-*(int*)b; } //调用主函数 qsort(a,n,sizeof(a[0]),cmp); //a待排序数组，n数组元素个数