SHARE
TWEET

Untitled

a guest Jul 17th, 2017 44 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <map>
  2. #include <iostream>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int A[] = {10,20,30,30,20,10,10,20};
  7.  
  8. // return (i, j) s.t. A[i] + ... + A[j] is nearest to value c
  9. pair<int, int> nearest_to_c(int c, int n, int A[]) {
  10.     map<int, int> bst;
  11.     bst[0] = -1;
  12.     // barriers
  13.     bst[-int(1e9)] = -2;
  14.     bst[int(1e9)] = n;
  15.  
  16.     int sum = 0, start, end, ret = c;
  17.     for (int i=0; i<n; ++i) {
  18.             sum += A[i];
  19.             // it->first >= sum-c, and with the minimal value in bst
  20.             map<int, int>::iterator it = bst.lower_bound(sum - c);
  21.             int tmp = -(sum - c - it->first);
  22.             if (tmp < ret) {
  23.                     ret = tmp;
  24.                     start = it->second + 1;
  25.                     end = i;
  26.             }
  27.  
  28.             --it;
  29.             // it->first < sum-c, and with the maximal value in bst
  30.             tmp = sum - c - it->first;
  31.             if (tmp < ret) {
  32.                     ret = tmp;
  33.                     start = it->second + 1;
  34.                     end = i;
  35.             }
  36.  
  37.             bst[sum] = i;
  38.     }
  39.     return make_pair(start, end);
  40. }
  41.  
  42. // demo
  43. int main() {
  44.     int c;
  45.     cin >> c;
  46.     pair<int, int> ans = nearest_to_c(c, 8, A);
  47.  
  48.     cout << ans.first << ' ' << ans.second << endl;
  49.     return 0;
  50. }
  51.    
  52. import java.util.*;
  53.  
  54. public class FindSubarrayClosestToZero {
  55.  
  56.     void findSubarrayClosestToZero(int[] A) {
  57.         int curSum = 0;
  58.         List<Pair> list = new ArrayList<Pair>();
  59.  
  60.         // 1. create prefix array: curSum array
  61.         for(int i = 0; i < A.length; i++) {
  62.             curSum += A[i];
  63.             Pair pair = new Pair(curSum, i);
  64.             list.add(pair);
  65.         }
  66.  
  67.         // 2. sort the prefix array by value
  68.         Collections.sort(list, valueComparator);
  69.  
  70.         // printPairList(list);
  71.         System.out.println();
  72.  
  73.  
  74.         // 3. compute pair-wise value diff: Triple< diff, i, i+1>
  75.         List<Triple> tList = new ArrayList<Triple>();
  76.         for(int i=0; i < A.length-1; i++) {
  77.             Pair p1 = list.get(i);
  78.             Pair p2 = list.get(i+1);
  79.             int valueDiff = p2.value - p1.value;
  80.  
  81.             Triple Triple = new Triple(valueDiff, p1.index, p2.index);          
  82.             tList.add(Triple);
  83.         }      
  84.  
  85.         // printTripleList(tList);
  86.         System.out.println();
  87.  
  88.         // 4. Sort by min diff
  89.         Collections.sort(tList, valueDiffComparator);
  90.         // printTripleList(tList);
  91.  
  92.         Triple res = tList.get(0);
  93.  
  94.         int startIndex = Math.min(res.index1 + 1, res.index2);
  95.         int endIndex = Math.max(res.index1 + 1, res.index2);
  96.  
  97.         System.out.println("nnThe subarray whose sum is closest to 0 is: ");
  98.         for(int i= startIndex; i<=endIndex; i++) {
  99.             System.out.print(" " + A[i]);
  100.         }
  101.     }
  102.  
  103.     class Pair {
  104.         int value;
  105.         int index;
  106.  
  107.         public Pair(int value, int index) {
  108.             this.value = value;
  109.             this.index = index;
  110.         }
  111.     }
  112.  
  113.     class Triple {
  114.         int valueDiff;
  115.         int index1;
  116.         int index2;
  117.  
  118.         public Triple(int valueDiff, int index1, int index2) {
  119.             this.valueDiff = valueDiff;
  120.             this.index1 = index1;
  121.             this.index2 = index2;
  122.         }
  123.     }
  124.  
  125.     public static Comparator<Pair> valueComparator = new Comparator<Pair>() {
  126.         public int compare(Pair p1, Pair p2) {
  127.             return p1.value - p2.value;
  128.         }
  129.     };      
  130.  
  131.     public static Comparator<Triple> valueDiffComparator = new Comparator<Triple>() {
  132.         public int compare(Triple t1, Triple t2) {
  133.             return t1.valueDiff - t2.valueDiff;
  134.         }
  135.     };
  136.  
  137.     void printPairList(List<Pair> list) {
  138.         for(Pair pair : list) {
  139.             System.out.println("<" + pair.value + " : " + pair.index + ">");
  140.         }
  141.     }
  142.  
  143.     void printTripleList(List<Triple> list) {
  144.         for(Triple t : list) {
  145.             System.out.println("<" + t.valueDiff + " : " + t.index1 + " , " + t.index2 + ">");
  146.         }
  147.     }
  148.  
  149.  
  150.     public static void main(String[] args) {
  151.         int A1[] = {8, -3, 2, 1, -4, 10, -5};       // -3, 2, 1
  152.         int A2[] = {-3, 2, 4, -6, -8, 10, 11};      // 2, 4, 6
  153.         int A3[] = {10, -2, -7};                                // 10, -2, -7
  154.  
  155.         FindSubarrayClosestToZero f = new FindSubarrayClosestToZero();
  156.         f.findSubarrayClosestToZero(A1);
  157.         f.findSubarrayClosestToZero(A2);
  158.         f.findSubarrayClosestToZero(A3);
  159.     }
  160. }
  161.    
  162. #include<bits/stdc++.h>
  163. #define M 1000010
  164. #define REP(i,n) for (int i=1;i<=n;i++)
  165. using namespace std;
  166. typedef long long ll;
  167. ll a[M],n,cum[M],ans=numeric_limits<ll>::max(); //cum->cumulative array
  168. int main() {
  169.     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  170.     cin>>n; REP(i,n) cin>>a[i],cum[i]=cum[i-1]+a[i];
  171.     sort(cum+1,cum+n+1);
  172.     REP(i,n-1) ans=min(ans,cum[i+1]-cum[i]);
  173.     cout<<ans; //min +ve difference from 0 we can get
  174. }
  175.    
  176. #include <map>
  177. #include <stdio.h>
  178. #include <algorithm>
  179. #include <limits.h>
  180.  
  181. using namespace std;
  182.  
  183. #define IDX_LOW_BOUND -2
  184.  
  185. // Return [i..j] range of A
  186. pair<int, int> nearest_to_c(int A[], int n, int t) {
  187.   map<int, int> bst;
  188.   int presum, subsum, closest, i, j, start, end;
  189.   bool unset;
  190.   map<int, int>::iterator it;
  191.  
  192.   bst[0] = -1;
  193.   // Barriers. Assume that no prefix sum is equal to INT_MAX or INT_MIN.
  194.   bst[INT_MIN] = IDX_LOW_BOUND;
  195.   bst[INT_MAX] = n;
  196.   unset = true;
  197.   // This initial value is always overwritten afterwards.
  198.   closest = 0;
  199.   presum = 0;
  200.   for (i = 0; i < n; ++i) {
  201.     presum += A[i];
  202.     for (it = bst.lower_bound(presum - t), j = 0; j < 2; --it, j++) {
  203.       if (it->first == INT_MAX || it->first == INT_MIN)
  204.         continue;
  205.       subsum = presum - it->first;
  206.       if (unset || abs(closest - t) > abs(subsum - t)) {
  207.         closest = subsum;
  208.         start = it->second + 1;
  209.         end = i;
  210.         if (closest - t == 0)
  211.           goto ret;
  212.         unset = false;
  213.       }
  214.     }
  215.     bst[presum] = i;
  216.   }
  217. ret:
  218.   return make_pair(start, end);
  219. }
  220.  
  221. int main() {
  222.   int A[] = {10, 20, 30, 30, 20, 10, 10, 20};
  223.   int t;
  224.   scanf("%d", &t);
  225.   pair<int, int> ans = nearest_to_c(A, 8, t);
  226.   printf("[%d:%d]n", ans.first, ans.second);
  227.   return 0;
  228. }
  229.    
  230. public class Solution {
  231.     /**
  232.      * @param nums: A list of integers
  233.      * @return: A list of integers includes the index of the first number
  234.      *          and the index of the last number
  235.      */
  236.     public ArrayList<Integer> subarraySumClosest(int[] nums) {
  237.         // write your code here
  238.         int len = nums.length;
  239.         ArrayList<Integer> result = new ArrayList<Integer>();
  240.         int[] sum = new int[len];
  241.         HashMap<Integer,Integer> mapHelper = new HashMap<Integer,Integer>();
  242.         int min = Integer.MAX_VALUE;
  243.         int curr1 = 0;
  244.         int curr2 = 0;
  245.         sum[0] = nums[0];
  246.         if(nums == null || len < 2){
  247.             result.add(0);
  248.             result.add(0);
  249.             return result;
  250.         }
  251.         for(int i = 1;i < len;i++){
  252.             sum[i] = sum[i-1] + nums[i];
  253.         }
  254.         for(int i = 0;i < len;i++){
  255.             if(mapHelper.containsKey(sum[i])){
  256.                 result.add(mapHelper.get(sum[i])+1);
  257.                 result.add(i);
  258.                 return result;
  259.             }
  260.             else{
  261.                 mapHelper.put(sum[i],i);
  262.             }
  263.         }
  264.         Arrays.sort(sum);
  265.         for(int i = 0;i < len-1;i++){
  266.             if(Math.abs(sum[i] - sum[i+1]) < min){
  267.                 min = Math.abs(sum[i] - sum[i+1]);
  268.                 curr1 = sum[i];
  269.                 curr2 = sum[i+1];
  270.             }
  271.         }
  272.         if(mapHelper.get(curr1) < mapHelper.get(curr2)){
  273.             result.add(mapHelper.get(curr1)+1);
  274.             result.add(mapHelper.get(curr2));
  275.         }
  276.         else{
  277.             result.add(mapHelper.get(curr2)+1);
  278.             result.add(mapHelper.get(curr1));
  279.         }
  280.         return result;
  281.     }
  282. }
RAW Paste Data
Top