差分+排序不等式+贪心 |
您所在的位置：网站首页 › 求整数序列中出现次数最多的数pta › 差分+排序不等式+贪心 |
差分+排序不等式+贪心
|
：加油加油，没几天就要比赛了
1.差分
差分的思想：给定a[1],a[2]…a[N],构造差分数组，使得a[i]=b[1]+b[2]+…b[i] 总的来说，a[i]就是b[1~i]的前缀和数组，那么构成a[i]的b[1],b[2]…b[i]就是差分数组. 其中b[i]=a[i]-a[i-1] 核心思想：如果要对a[l~r]全部都+c,等价于b[l]+=c,b[r+1]-=c; 题目： 输入一个长度为 n 的整数序列。接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r] 之间的每个数加上 c。请你输出进行完所有操作后的序列。 代码： //差分 时间复杂度 o(m) #include using namespace std; const int N = 1e5 + 10; int a[N], b[N]; int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i scanf("%d%d%d", &l, &r, &c); b[l] += c; //将序列中[l, r]之间的每个数都加上c b[r + 1] -= c; } for (int i = 1; i cin >> n; for (int i = 0; i > a[i]; sort(a, a + n); long long res = 0; // WA后就知道开long long 了.. for (int i = 0; i scanf("%d", &arr[i]); } int m; cin >> m; while (m -- ){ int l, r; scanf("%d%d", &l, &r); cnt[l]++;//一维差分 //目的：使得l~r的出现次数都增加1 cnt[r + 1]--;//一维差分，使r+1~n出现次数保持不变 } for(int i = 1; i //结果总和=每个位置查询的次数乘以该位置上的数字 sumA += cnt[i] * arr[i]; //原数组之和 } /* 因为较大的值 4 5 已经与 较大的次数 2 2 正好对应了。 所以两个 数组全部排序，再遍历一遍，进行求和就性 arr[]: 1 2 3 4 5 cnt[]: 1 1 1 2 2 */ long long sumB = 0; sort(arr + 1, arr + n + 1); sort(cnt + 1, cnt + n + 1); for(int i = 1; i int k; cin >> k; cin >> s; int l = s.size(); if (l % k != 0) { cout ss[j]+= s[i]; i++; t++; } else { t = 0; j++; } } /* 1.求子串的方法： for (int i = 0; i < s.size(); i=i+t) { string x = s.substr(i, t);//substr(起始位置，终止位置) v.push_back(x); } 2.此处可以不必求子串，直接遍历就好 for (int i = 0; i < m; i++) { for (int j = i; j < l; ) { cnt[s[j] - 'a']++; j += m; } int ma = *max_element(cnt, cnt + 50); ans += k - ma; memset(cnt, 0, sizeof cnt); } */ for (int i = 0; i cnt[ss[t][i] - 'a']++; } int ma = *max_element(cnt,cnt+50);//求正确字符的出现次数 ans += k - ma;//k-正确字符的个数就是修改的次数 memset(cnt, 0, sizeof cnt); //fill(cnt, cnt + 26, 0);fill可以把初值设为任意值，memset只能设为0/-1 } cout |
相当于: 1.a[1~l-1]无影响 2.a[l~r]加c 3.a[r+1~n]无影响【本文地址】
今日新闻 |
推荐新闻 |