博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
K-Anonymous Sequence
阅读量:5924 次
发布时间:2019-06-19

本文共 3457 字,大约阅读时间需要 11 分钟。

                                                                                                                                                     K-Anonymous Sequence
Time Limit: 4000MS   Memory Limit: 65536K
Total Submissions: 6525   Accepted: 2173

Description

The explosively increasing network data in various application domains has raised privacy concerns for the individuals involved. Recent studies show that simply removing the identities of nodes before publishing the graph/social network data does not guarantee privacy. The structure of the graph itself, along with its basic form the degree of nodes, can reveal the identities of individuals.

To address this issue, we study a specific graph-anonymization problem. We call a graph k-anonymous if for every node v, there exist at least k-1 other nodes in the graph with the same degree as v. And we are interested in achieving k-anonymous on a graph with the minimum number of graph-modification operations.

We simplify the problem. Pick 
n nodes out of the entire graph 
G and list their degrees in ascending order. We define a sequence 
k-anonymous if for every element 
s, there exist at least 
k-1 other elements in the sequence equal to 
s. To let the given sequence 
k-anonymous, you could do one operation only—decrease some of the numbers in the sequence. And we define the cost of the modification the sum of the difference of all numbers you modified. e.g. sequence 2, 2, 3, 4, 4, 5, 5, with 
k=3, can be modified to 2, 2, 2, 4, 4, 4, 4, which satisfy 3-anonymous property and the cost of the modification will be |3-2| + |5-4| + |5-4| = 3.

Give a sequence with n numbers in ascending order and k, we want to know the modification with minimal cost among all modifications which adjust the sequence k-anonymous.

Input

The first line of the input file contains a single integer T (1 ≤ T ≤ 20) – the number of tests in the input file. Each test starts with a line containing two numbers n (2 ≤ n ≤ 500000) – the amount of numbers in the sequence and k (2 ≤ k ≤ n). It is followed by a line with n integer numbers—the degree sequence in ascending order. And every number s in the sequence is in the range [0, 500000].

Output

For each test, output one line containing a single integer—the minimal cost.

Sample Input

27 32 2 3 4 4 5 56 20 3 3 4 8 9

Sample Output

35

Source

思路:Fi=min(Fj+sum[i]sum[j](ij)×a(j+1))Fi=min(Fj+sum[i]−sum[j]−(i−j)×a(j+1)) 0<=j<=ik.  套斜率dp即可。

#include
#include
#include
#include
#include
#define N 300010#define maxn 500005#define REP(i, a, b) for(int i = (a); i <= (b); ++ i)#define REP(j, a, b) for(int j = (a); j <= (b); ++ j)#define PER(i, a, b) for(int i = (a); i >= (b); -- i)const long long inf=1LL<<61;using namespace std;template
inline void rd(T &ret){ char c; ret = 0; while ((c = getchar()) < '0' || c > '9'); while (c >= '0' && c <= '9'){ ret = ret * 10 + (c - '0'), c = getchar(); }}long long p[maxn],dp[maxn],sum[maxn],q[maxn];int T,n,k;double slope(int u,int v){ double y=dp[v]-sum[v]+v*p[v+1]-dp[u]+sum[u]-u*p[u+1]; double x=p[v+1]-p[u+1]; if(!x&&!y)return inf; return y/x;}int main(){ rd(T); while(T--){ rd(n),rd(k); for(int i=1;i<=n;i++){ scanf("%d",&p[i]); sum[i]=sum[i-1]+p[i]; } REP(i, k, n)dp[i]=sum[i]-i*p[1]; REP(i, 0, k-1)dp[i]=inf; int h=1,t=1; q[1]=k; REP(i, k, n){ while(h
<=i)h++; dp[i] = min(dp[i], dp[q[h]] + sum[i] - sum[q[h]] - (i - q[h]) * p[q[h] + 1]); while(h
<=slope(q[t-1],q[t]))t--; q[++t]=i-k+1; } cout<
<

 

转载于:https://www.cnblogs.com/czy-power/p/10365824.html

你可能感兴趣的文章
DNS and Bind 以及DNS服务器的构建
查看>>
SSL ×××原理介绍 IPsec原理
查看>>
WindowsPhone操作SkyDrive之获取共享文件
查看>>
Project Server 2013新手入门 (一)为PWA添加用户并分享网站
查看>>
MongoDB: 1. Database
查看>>
使用VBS脚本实现的Hosts文件一键配置
查看>>
ATOM插件activate-power-mode体验笔记
查看>>
socket 和 http
查看>>
九、redis高可用
查看>>
RMAN-08137: WARNING: archived log not deleted, needed for standby or upstream capture process
查看>>
限制Textarea字数并实时显示输入字数统计
查看>>
RPC OVER HTTPS
查看>>
linux的top命令参数详解
查看>>
净空法师:人到这个世间来干什么?做人的意义究竟在哪里?
查看>>
洪泛和广播的区别
查看>>
思科IOS软件命名规则
查看>>
Windows Update的自动更新被关闭了,并且更改按钮是灰色无法更改设置
查看>>
Debian kali2 操作系统Segmentation fault
查看>>
oracle中Where子句顺序是否对SQL性能有影响
查看>>
开源邮件服务器
查看>>