spoj 274

时间:2022-12-24 20:15:37

离散化   枚举行  扫描横坐标

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 0x7fffffff
using namespace std; struct cc
{
int x,y,val;
};
cc pp[1010];
int k,line[1010],x[1010],cur;
int _max,_min; int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d%d",&n,&k);
_max = -1;
_min = inf;
for(int i = 0; i < n; i++)
{
scanf("%d%d%d",&pp[i].x,&pp[i].y,&pp[i].val);
line[i] = pp[i].y;
_max = max(pp[i].x, _max);
_min = min(pp[i].x, _min);
}
sort(line, line+n);
int q = unique(line, line+n) - line;
// if(q == 1)
// {
// puts("0");
// continue;
// }
int ans = inf;
for(int i = 0; i < q; i++)
{
for(int j = i; j < q; j++)
{
memset(x, 0, sizeof(x));
for(int v = 0; v < n; v++)
{
if(pp[v].y >= line[i] && pp[v].y <= line[j])
x[pp[v].x] += pp[v].val;
}
int l,r;
l = r = _min;
cur = x[_min];
while(r <= _max)
{
if(cur >= k)
{
ans = min(ans, (line[j]-line[i])*(r-l));
cur -= x[l++];
}
else
{
cur += x[++r];
}
}
}
}
printf("%d\n",ans);
}
return 0;
}

spoj 274的更多相关文章

  1. SPOJ 274 Johnny and the Watermelon Plantation(TLE)

    O(n^3)的时间复杂度,改了半天交了二三十遍,TLE到死,实在没办法了…… 跪求指点!!! #include <cstdio> #include <cstdlib> #inc ...

  2. BZOJ 2588&colon; Spoj 10628&period; Count on a tree &lbrack;树上主席树&rsqb;

    2588: Spoj 10628. Count on a tree Time Limit: 12 Sec  Memory Limit: 128 MBSubmit: 5217  Solved: 1233 ...

  3. SPOJ DQUERY D-query(主席树)

    题目 Source http://www.spoj.com/problems/DQUERY/en/ Description Given a sequence of n numbers a1, a2, ...

  4. SPOJ GSS3 Can you answer these queries III&lbrack;线段树&rsqb;

    SPOJ - GSS3 Can you answer these queries III Description You are given a sequence A of N (N <= 50 ...

  5. 【填坑向】spoj COT&sol;bzoj2588 Count on a tree

    这题是学主席树的时候就想写的,,, 但是当时没写(懒) 现在来填坑 = =日常调半天lca(考虑以后背板) 主席树还是蛮好写的,但是代码出现重复,不太好,导致调试的时候心里没底(虽然事实证明主席树部分 ...

  6. SPOJ bsubstr

    题目大意:给你一个长度为n的字符串,求出所有不同长度的字符串出现的最大次数. n<=250000 如:abaaa 输出: 4 2 1 1 1 spoj上的时限卡的太严,必须使用O(N)的算法那才 ...

  7. 【SPOJ 7258】Lexicographical Substring Search

    http://www.spoj.com/problems/SUBLEX/ 好难啊. 建出后缀自动机,然后在后缀自动机的每个状态上记录通过这个状态能走到的不同子串的数量.该状态能走到的所有状态的f值的和 ...

  8. 【SPOJ 1812】Longest Common Substring II

    http://www.spoj.com/problems/LCS2/ 这道题想了好久. 做法是对第一个串建后缀自动机,然后用后面的串去匹配它,并在走过的状态上记录走到这个状态时的最长距离.每匹配完一个 ...

  9. 【SPOJ 8222】Substrings

    http://www.spoj.com/problems/NSUBSTR/ clj课件里的例题 用结构体+指针写完模板后发现要访问所有的节点,改成数组会更方便些..于是改成了数组... 这道题重点是求 ...

随机推荐

  1. unity3d 射弹基础案例代码分析

    #pragma strict import UnityEngine.UI; function Start () { } var speed : int = 5; var newobject : Tra ...

  2. ManualResetEvent详解

    原文来自:http://www.cnblogs.com/tianzhiliang/archive/2011/03/04/1970726.html 1. 源码下载: 下载地址:http://files. ...

  3. python:页面布局 后台管理页面之常用布局

    <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/ ...

  4. 2014 Asia AnShan Regional Contest --- HDU 5078 Osu&excl;

    Osu! Problem's Link:   http://acm.hdu.edu.cn/showproblem.php?pid=5078 Mean: 略. analyse: 签到题,直接扫一遍就得答 ...

  5. Java for LeetCode 164 Maximum Gap

    Given an unsorted array, find the maximum difference between the successive elements in its sorted f ...

  6. (转)从工程中删除Cocoapods

    1. 删除工程文件夹下的Podfile.Podfile.lock及Pods文件夹 2. 删除xcworkspace文件 3. 使用xcodeproj文件打开工程,删除Frameworks组下的Pods ...

  7. JSON对象(自定义对象)

    JSON对象(自定义对象) 1.什么是JSON对象 JSON对象是属性的无序集合,在内存中也表现为一段连续的内存地址(堆内存) 1)JSON对象是属性的集合 2)这个集合是没有任何顺序的 2.JSON ...

  8. Java SE基础部分——常用类库之NumberFormat(数字格式化)

    数字格式化常用方法:DecimalFormat和NuberFormat. //2016060524 数字格式化学习 //数字格式化 两种方法 一种直接使用NumberFormat,另一种Decimal ...

  9. MFC 只启动一个程序实例

    问题描述: 我们开发过程中可能会经常遇到,只启动一个程序实例.即一个程序启动之后,如果再次执行该程序,将会恢复之前打开的程序,而不是打开一个新的程序. 实现原理:利用FindWindow/FindWi ...

  10. SoapUI中XML解析

    From http://www.robert-nemet.com/2011/11/groovy-xml-parsing-in-soapui.html Introduction Since soapUI ...